Please answer this : #3 A min-max heap is a data structure that supports both de

Question

Please answer this :

#3 A min-max heap is a data structure that supports both deleteMin and deleteMax in O(logN) per operation. The structure is identical to a binary heap, but the heaporder property is that for any node, X, at even depth, the element stored at X is smaller than the parent but larger than the grandparent (where this makes sense), and for any node X at odd depth, the element stored at X is larger than the parent but smaller than the grandparent. See Figure 6.57. a. How do we find the minimum and maximum elements? b. Give an algorithm to insert a new node into the min-max heap. c. Give an algorithm to perform deleteMin and deleteMax. d. Can you build a min-max heap in linear time? 81 87 12 28 80 52 42 71 25 20 78 31 31 59) 16) 24) 79 63 18 19 32 (13) (15 48

Explanation / Answer

a) The root is the min element.And the max element can be found out by comparing the two child of the two root the bigger element between the two child nodes of the root is the max element.

b)Insertion in minmax heap

To add an element to a Min-Max Heap perform following operations:

Insert the required key into given Min-Max Heap.

Compare this key with its parent. If it is found to be smaller (greater) compared to its parent, then it is surely smaller (greater) than all other keys present at nodes at max(min) level that are on the path from the present position of key to the root of heap. Now, just check for nodes on Min(Max) levels.

If the key added is in correct order then stop otherwise swap that key with its parent.

Psuedocode:

void min_max_insert(element heap[],int n,element item)
{
/* insert item into the min-max heap*/
int parent;
(*n)++;
if(*n==MAX_SIZE)
{
fprintf(stderr,

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---