A min-max heap is a data structure that supports both deleteMin and deleteMax in

Question

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 the grandparent. See Figure 6.58. How do we find the minimum and maximum elements? Give an algorithm to insert a new node into the min-max heap. Give an algorithm to perform deleteMin and deleteMax. Can you build a min-max heap in linear time? Suppose we would like to support deleteMin, deleteMax, and merge. Propose a data structure to support all operations in O(log N) time.

Explanation / Answer

a) As for definition

root node is minimum element

and maximum element is one of the two childrens of the root, i.e maximum value of these childrens.

b)

from definiton we know that even levels are MIN levels and odd levels are MAX levels.

For inserting a key,

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.

c)

procedure DeleteMin
1. MinItem <- A[root]
2. NewItem <- last leaf of the heap
3. Remove the last leaf from the heap
4. Detect the chain C consisting of smallergrandchild(root),
smaller-grandchild(smallergrandchild(root))...
5. if the last member is not a leaf then
include its child to the chain C
6. Use binary search to find the place m in C, so
that inserting NewItem in position m in C keeps it
sorted
7. for all nodes k above position m in the chain, in
increasing order of k
A[grandparent(k)] <- A[k]
Update bit-field of parent(grandparent(k))
8. Place NewItem to the position m in C, and
update its parent’s bit-field.
9. return MinItem
end procedure

The DeleteMax procedure is essentially the same
except that we are to start from the larger son of the
root, instead of the root itself and the chain consists
of smaller-grandchildren, instead of the larger ones.

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.