(a) Suppose we inserted entries with keys 1, 2, ..., 6 into a heap. Mark all...

 

Transcribed Image Text:

(a) Suppose we inserted entries with keys 1, 2, ..., 6 into a heap. Mark all nodes that can contain the entry with key 5 in a i. min-oriented heap. ii. max-oriented heap. (b) Let H and H be two min-oriented heaps with n and n entries, respectively. Show that the entries of H and H can be combined into a single min-oriented heap in time O(n + n) (i.e. linear in the number of total entries). You may assume that the heaps are array-based and those arrays are public access. (a) Suppose we inserted entries with keys 1, 2, ..., 6 into a heap. Mark all nodes that can contain the entry with key 5 in a i. min-oriented heap. ii. max-oriented heap. (b) Let H and H be two min-oriented heaps with n and n entries, respectively. Show that the entries of H and H can be combined into a single min-oriented heap in time O(n + n) (i.e. linear in the number of total entries). You may assume that the heaps are array-based and those arrays are public access.