10.3 Discussion and Exercises

The implicit representation of a complete binary tree as an array, or list, seems to have been first proposed by Eytzinger [24], as a representation for pedigree family trees. The $\mathtt{BinaryHeap}$ data structure described here was first introduced by Williams [69].

The randomized $\mathtt{MeldableHeap}$ data structure described here appears to have first been proposed by Gambin and Malinowski [31]. Other meldable heap implementations exist, including leftist heaps [13,43, Section 5.3.2], binomial heaps [66], Fibonacci heaps [29], pairing heaps [28], and skew heaps [63], although none of these are as simple as the $\mathtt{MeldableHeap}$ structure.

Some of the above structures also support a $\mathtt{decreaseKey(u,y)}$ operation in which the value stored at node $\mathtt{u}$ is decreased to $\mathtt{y}$. (It is a pre-condition that $\ensuremath{\mathtt{y}}\le\ensuremath{\mathtt{u.x}}$.) This operation can be implemented in $O(\log \ensuremath{\mathtt{n}})$ time in most of the above structures by removing node $\mathtt{u}$ and adding $\mathtt{y}$. However, some of these structures can implement $\mathtt{decreaseKey(u,y)}$ more efficiently. In particular, $\mathtt{decreaseKey(u,y)}$ takes $O(1)$ amortized time in Fibonacci heaps and $O(\log\log \ensuremath{\mathtt{n}})$ amortized time in a special version of pairing heaps [22]. This more efficient $\mathtt{decreaseKey(u,y)}$ operation has applications in speeding up several graph algorithms including Dijkstra's shortest path algorithm [29].

Exercise 10..1   Illustrate the addition of the values 7 and then 3 to the $\mathtt{BinaryHeap}$ shown at the end of Figure 10.2.

Exercise 10..2   Illustrate the removal of the next two values (6 and 8) on the $\mathtt{BinaryHeap}$ shown at the end of Figure 10.3.

Exercise 10..3   Implement the $\mathtt{remove(i)}$ method, that removes the value stored in $\mathtt{a[i]}$ in a $\mathtt{BinaryHeap}$. This method should run in $O(\log \ensuremath{\mathtt{n}})$ time. Next, explain why this method is not likely to be useful.

Exercise 10..4   A $d$-ary tree is a generalization of a binary tree in which each internal node has $d$ children. Using Eytzinger's method it is also possible to represent complete $d$-ary trees using arrays. Work out the equations that, given an index $\mathtt{i}$, determine the index of $\mathtt{i}$'s parent and each of $\mathtt{i}$'s $d$ children in this representation.

Exercise 10..5   Using what you learned in Exercise 10.4, design and implement a $\mathtt{DaryHeap}$, the $d$-ary generalization of a $\mathtt{BinaryHeap}$. Analyze the running times of operations on a $\mathtt{DaryHeap}$ and test the performance of your $\mathtt{DaryHeap}$ implementation against that of the $\mathtt{BinaryHeap}$ implementation given here.

Exercise 10..6   Illustrate the addition of the values 17 and then 82 in the $\mathtt{MeldableHeap}$ $\mathtt{h1}$ shown in Figure 10.4. Use a coin to simulate a random bit when needed.

Exercise 10..7   Illustrate the removal of the next two values (4 and 8) in the $\mathtt{MeldableHeap}$ $\mathtt{h1}$ shown in Figure 10.4. Use a coin to simulate a random bit when needed.

Exercise 10..8   Implement the $\mathtt{remove(u)}$ method, that removes the node $\mathtt{u}$ from a $\mathtt{MeldableHeap}$. This method should run in $O(\log \ensuremath{\mathtt{n}})$ expected time.

Exercise 10..9   Show how, in a $\mathtt{BinaryHeap}$ or $\mathtt{MeldableHeap}$, to find the second smallest value in constant time.

Exercise 10..10   Show how, in a $\mathtt{BinaryHeap}$ or $\mathtt{MeldableHeap}$, to find the $k$th smallest value in $O(k\log k)$ time. (Hint: Using another heap might help.)

Exercise 10..11   Suppose you are given $\mathtt{k}$ sorted lists, of total length $\mathtt{n}$. Show how, using a heap, to merge these into a single sorted list in $O(n\log k)$ time. (Hint: Starting with the case $k=2$ can be instructive.)