• 10 Heaps
• 10.1 BinaryHeap: An Implicit Binary Tree
• 10.1.1 Summary
• 10.2 MeldableHeap: A Randomized Meldable Heap
• 10.2.1 Analysis of merge(h1,h2)
• 10.2.2 Summary
• 10.3 Discussion and Exercises

In this chapter, we discuss two implementations of the extremely useful priority Queue data structure. Both of these structures are a special kind of binary tree called a heap, which means “a disorganized pile.” This is in contrast to binary search trees that can be thought of as a highly organized pile.

The first heap implementation uses an array to simulate a complete binary tree. This very fast implementation is the basis of one of the fastest known sorting algorithms, namely heapsort (see Section 11.1.3). The second implementation is based on more flexible binary trees. It supports a meld(h) operation that allows the priority queue to absorb the elements of a second priority queue h.

10.1 BinaryHeap: An Implicit Binary Tree

Our first implementation of a (priority) Queue is based on a technique that is over four hundred years old. Eytzinger's method allows us to represent a complete binary tree as an array by laying out the nodes of the tree in breadth-first order (see Section 6.1.2). In this way, the root is stored at position 0, the root's left child is stored at position 1, the root's right child at position 2, the left child of the left child of the root is stored at position 3, and so on. See Figure 10.1.

Figure 10.1 Eytzinger's method represents a complete binary tree as an array.

If we apply Eytzinger's method to a sufficiently large tree, some patterns emerge. The left child of the node at index i is at index \(\texttt{left(i)}=2\texttt{i}+1\) and the right child of the node at index i is at index \(\texttt{right(i)}=2\texttt{i}+2\). The parent of the node at index i is at index \(\texttt{parent(i)}=(\texttt{i}-1)/2\).

    int left(int i) {
        return 2*i + 1;
    }
    int right(int i) {
        return 2*i + 2;
    }
    int parent(int i) {
        return (i-1)/2;
    }

A BinaryHeap uses this technique to implicitly represent a complete binary tree in which the elements are heap-ordered: The value stored at any index i is not smaller than the value stored at index parent(i), with the exception of the root value, \(\texttt{i}=0\). It follows that the smallest value in the priority Queue is therefore stored at position 0 (the root).

In a BinaryHeap, the n elements are stored in an array a:

    T[] a;
    int n;

Implementing the add(x) operation is fairly straightforward. As with all array-based structures, we first check to see if a is full (by checking if \(\texttt{a.length}=\texttt{n}\)) and, if so, we grow a. Next, we place x at location a[n] and increment n. At this point, all that remains is to ensure that we maintain the heap property. We do this by repeatedly swapping x with its parent until x is no longer smaller than its parent. See Figure 10.2.

    boolean add(T x) {
        if (n + 1 > a.length) resize();
        a[n++] = x;
        bubbleUp(n-1);
        return true;
    }
    void bubbleUp(int i) {
        int p = parent(i);
        while (i > 0 && c.compare(a[i], a[p]) < 0) {
            swap(i,p);
            i = p;
            p = parent(i);
        }
    }

Figure 10.2 Adding the value 6 to a BinaryHeap.

Implementing the remove() operation, which removes the smallest value from the heap, is a little trickier. We know where the smallest value is (at the root), but we need to replace it after we remove it and ensure that we maintain the heap property.

The easiest way to do this is to replace the root with the value a[n-1], delete that value, and decrement n. Unfortunately, the new root element is now probably not the smallest element, so it needs to be moved downwards. We do this by repeatedly comparing this element to its two children. If it is the smallest of the three then we are done. Otherwise, we swap this element with the smallest of its two children and continue.

    T remove() {
        T x = a[0];
        a[0] = a[--n];
        trickleDown(0);
        if (3*n < a.length) resize();
        return x;
    }
    void trickleDown(int i) {
        do {
            int j = -1;
            int r = right(i);
            if (r < n && c.compare(a[r], a[i]) < 0) {
                int l = left(i);
                if (c.compare(a[l], a[r]) < 0) {
                    j = l;
                } else {
                    j = r;
                }
            } else {
                int l = left(i);
                if (l < n && c.compare(a[l], a[i]) < 0) {
                    j = l;
                }
            }
            if (j >= 0)    swap(i, j);
            i = j;
        } while (i >= 0);
    }

Figure 10.3 Removing the minimum value, 4, from a BinaryHeap.

As with other array-based structures, we will ignore the time spent in calls to resize(), since these can be accounted for using the amortization argument from Lemma 2.1. The running times of both add(x) and remove() then depend on the height of the (implicit) binary tree. Luckily, this is a complete binary tree; every level except the last has the maximum possible number of nodes. Therefore, if the height of this tree is \(h\), then it has at least \(2^h\) nodes. Stated another way \begin{equation*} \texttt{n} \ge 2^h \enspace . \end{equation*} Taking logarithms on both sides of this equation gives \begin{equation*} h \le \log \texttt{n} \enspace . \end{equation*} Therefore, both the add(x) and remove() operation run in \(O(\log \texttt{n})\) time.

10.1.1 Summary

The following theorem summarizes the performance of a BinaryHeap:

10.2 MeldableHeap: A Randomized Meldable Heap

In this section, we describe the MeldableHeap, a priority Queue implementation in which the underlying structure is also a heap-ordered binary tree. However, unlike a BinaryHeap in which the underlying binary tree is completely defined by the number of elements, there are no restrictions on the shape of the binary tree that underlies a MeldableHeap; anything goes.

The add(x) and remove() operations in a MeldableHeap are implemented in terms of the merge(h1,h2) operation. This operation takes two heap nodes h1 and h2 and merges them, returning a heap node that is the root of a heap that contains all elements in the subtree rooted at h1 and all elements in the subtree rooted at h2.

The nice thing about a merge(h1,h2) operation is that it can be defined recursively. See Figure 10.4. If either h1 or h2 is nil, then we are merging with an empty set, so we return h2 or h1, respectively. Otherwise, assume \(\texttt{h1.x} \le \texttt{h2.x}\) since, if \(\texttt{h1.x} > \texttt{h2.x}\), then we can reverse the roles of h1 and h2. Then we know that the root of the merged heap will contain h1.x, and we can recursively merge h2 with h1.left or h1.right, as we wish. This is where randomization comes in, and we toss a coin to decide whether to merge h2 with h1.left or h1.right:

    Node<T> merge(Node<T> h1, Node<T> h2) {
        if (h1 == nil) return h2;
        if (h2 == nil) return h1;
        if (c.compare(h2.x, h1.x) < 0) return merge(h2, h1);
        // now we know h1.x <= h2.x
        if (rand.nextBoolean()) {
            h1.left = merge(h1.left, h2);
            h1.left.parent = h1;
        } else {
            h1.right = merge(h1.right, h2);
            h1.right.parent = h1;
        }
        return h1;
    }

Figure 10.4 Merging h1 and h2 is done by merging h2 with one of h1.left or h1.right.

In the next section, we show that merge(h1,h2) runs in \(O(\log \texttt{n})\) expected time, where n is the total number of elements in h1 and h2.

With access to a merge(h1,h2) operation, the add(x) operation is easy. We create a new node u containing x and then merge u with the root of our heap:

    boolean add(T x) {
        Node<T> u = newNode();
        u.x = x;
        r = merge(u, r);
        r.parent = nil;
        n++;
        return true;
    }

The remove() operation is similarly easy. The node we want to remove is the root, so we just merge its two children and make the result the root:

    T remove() {
        T x = r.x;
        r = merge(r.left, r.right);
        if (r != nil) r.parent = nil;
        n--;
        return x;
    }

Additionally, a MeldableHeap can implement many other operations in \(O(\log \texttt{n})\) expected time, including:

• remove(u): remove the node u (and its key u.x) from the heap.
• absorb(h): add all the elements of the MeldableHeap h to this heap, emptying h in the process.

10.2.1 Analysis of merge(h1,h2)

The analysis of merge(h1,h2) is based on the analysis of a random walk in a binary tree. A random walk in a binary tree starts at the root of the tree. At each step in the random walk, a coin is tossed and, depending on the result of this coin toss, the walk proceeds to the left or to the right child of the current node. The walk ends when it falls off the tree (the current node becomes nil).

The following lemma is somewhat remarkable because it does not depend at all on the shape of the binary tree:

We make a quick digression to note that, for readers who know a little about information theory, the proof of Lemma 10.1 can be stated in terms of entropy.

With this result on random walks, we can now easily prove that the running time of the merge(h1,h2) operation is \(O(\log \texttt{n})\).

10.2.2 Summary

The following theorem summarizes the performance of a MeldableHeap:

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]. He used this representation in books containing pedigree family trees of noble families. The BinaryHeap data structure described here was first introduced by Williams [78].

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], binomial heaps [75], Fibonacci heaps [30], pairing heaps [29], and skew heaps [72], although none of these are as simple as the MeldableHeap structure.

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