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.)

opendatastructures.org