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

opendatastructures.org