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

The randomized MeldableHeap data structure described here appears to have first been proposed by Gambin and Malinowski [29]. Other meldable heap implementations exist, including leftist heaps [12,41, Section 5.3.2], binomial heaps [62], Fibonacci heaps [27], pairing heaps [26], and skew heaps [61], 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 [20]. This more efficient $\mathtt{decreaseKey(u,y)}$ operation has applications in speeding up several graph algorithms including Dijkstra's shortest path algorithm [27].