![[topimage]](IMADA_en.png)
Exercises
- Show that there is at most a logarithmic number of nodes on the right-most path in a leftist heap with n element. Hint: Show that a node of rank r has exponentially many nodes in its subtree. Then consider how ranks behave on the right-most path.
- How can the operations decreasekey, delete, and update (could be increase as well as decrease) be implemented to run in time O(log n) for leftist heaps? It is assumed that you are given a reference to the element and you may introduce additional references in the structure. Hint: Some operations can be reduced to others.
- [CLRS09] 17.3-3, 17.3-6.
- Come up with an implementation of a queue (not priority queue), where, in addition to the usual operations enqueue and dequeue, there is an operation findmin that reports the minimum element in the queue (assuming we have a total ordering on the elements). All operations should be OA(1). You may assume that all elements in the queue at a given time are unique.
- For skew heaps, what if we define heavy as |Tr(x)| ≥ ¾ |Tx|? Or |Tr(x)| ≥ ¼ |Tx|? How does that affect the analysis?
- One can probably easily imagine scenarios where leftist heaps are preferable to skew heaps, but what if you are just interested in the final result of running an algorithm on n elements and during the course of the algorithm, one has to merge priority queues n times. Which priority queue implementation do you think would be best?
- Here is an alternative to leftist heaps: As for leftist heaps, we consider binary heap-ordered trees. However, instead of rank, each node has a size attribute, storing the size of the subtree in which it is a root. Just as for leftist heaps, we define meld, and then all other operations follow from that. The meld operation is defined as follows. Assume that we want to meld X and Y, and assume that X has the smallest key k in the root (otherwise we just switch the two arguments) and that its two subtrees are Xleft and Xright. Now sort the trees Xleft, Xright, and Y in non-decreasing order of size and name them A, B, and C, i.e., A.size ≤ B.size ≤ C.size. Make a node that has k in the root and the two subtrees meld(A,B) and C. Consider correctness and complexity.
- Repetition (should be known from DM507): Show that two standard heaps with 2p-1 elements each plus one extra element x can be combined into one heap in time O(p). The heaps are representd as trees with nodes and references to other nodes, i.e., not the array-implementation. Show that a standard heap can be build out of n=2p-1 elements in time O(n) by a bottom-up application of the result above. Given n elements, how can a leftist heap be constructed in time O(n)?