1. A min-max heap is a data Structure that supports both deleteMin and deleteMax
ID: 3863811 • Letter: 1
Question
1. 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 heap-order 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 grandparent.
Give an algorithm to insert a new node into the min-max heap.
81 87 17 14 12 78 71 80 20 31) 59) 16 (24) 79) 63) 18) (19) 32) 13) 15) 48 Figure 6.57 Min-max heap 31 28Explanation / Answer
1a) 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.
1b)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, The heap is full );
exit(1);
}
parent = (*n)/2;
if (!parent)
/* heap is empty, insert item into first position */
heap[1] = item;
else switch(level(parent)) {
case FALSE:/*min level*/
if (item.key<heap[parent].key) {
heap[*n]=heap[parent];
verify_min(heap,parent,item);
}
else
verify_max(heap,*n,item);
break;
case TRUE; /*max level*/
if (item.key > heap[parent].key) {
heap[*n]=heap[parent];
verify_max(heap, parent, item);
}
else
verify_min(heap,*n,item);
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.