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 [27], as a representation for pedigree family trees. The BinaryHeap data structure described here was first introduced by Williams [76].

The randomized MeldableHeap data structure described here appears to have first been proposed by Gambin and Malinowski [34]. Other meldable heap implementations exist, including leftist heaps [16,48, Section 5.3.2], binomial heaps [73], Fibonacci heaps [32], pairing heaps [31], and skew heaps [70], although none of these are as simple as the 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 [25]. This more efficient $\mathtt{decreaseKey(u,y)}$ operation has applications in speeding up several graph algorithms including Dijkstra's shortest path algorithm [32].

Exercise 10..1   Illustrate the addition of the values 7 and then 3 to the 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 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 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 DaryHeap, the $d$-ary generalization of a BinaryHeap. Analyze the running times of operations on a DaryHeap and test the performance of your DaryHeap implementation against that of the BinaryHeap implementation given here.

Exercise 10..6   Illustrate the addition of the values 17 and then 82 in the 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 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 MeldableHeap. This method should run in $O(\log \ensuremath{\mathtt{n}})$ expected time.

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

Exercise 10..10   Show how, in a BinaryHeap or 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.)