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.

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);
}
}
```

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);
}
```

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`

:

`BinaryHeap`

implements the (priority) `Queue`

interface. Ignoring
the cost of calls to `resize()`

, a `BinaryHeap`

supports the operations
`add(x)`

and `remove()`

in \(O(\log \texttt{n})\) time per operation.
Furthermore, beginning with an empty `BinaryHeap`

, any sequence of \(m\)
`add(x)`

and `remove()`

operations results in a total of \(O(m)\)
time spent during all calls to `resize()`

.

# 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;
}
```

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.

`merge(h1,h2)`

operations that each take \(O(\log \texttt{n})\) expected time.
## 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:

`n`

nodes is at most `\log (n+1)`

.

`n`

. In the base case, \(\texttt{n}=0\) and the walk
has length \(0=\log (\texttt{n}+1)\). Suppose now that the result is true for
all non-negative integers \(\texttt{n}'< \texttt{n}\).
Let \(\texttt{n}_1\) denote the size of the root's left subtree, so that
\(\texttt{n}_2=\texttt{n}-\texttt{n}_1-1\) is the size of the root's right subtree. Starting at
the root, the walk takes one step and then continues in a subtree of
size \(\texttt{n}_1\) or \(\texttt{n}_2\). By our inductive hypothesis, the expected
length of the walk is then
\begin{equation*}
\E[W] = 1 + \frac{1}{2}\log (\texttt{n}_1+1) + \frac{1}{2}\log (\texttt{n}_2+1) \enspace ,
\end{equation*}
since each of \(\texttt{n}_1\) and \(\texttt{n}_2\) are less than \(\texttt{n}\). Since \(\log\)
is a concave function, \(\E[W]\) is maximized when \(\texttt{n}_1=\texttt{n}_2=(\texttt{n}-1)/2\).
Therefore,
the expected number of steps taken by the random walk is
\begin{align*}
\E[W]
& = 1 + \frac{1}{2}\log (\texttt{n}_1+1) + \frac{1}{2}\log (\texttt{n}_2+1) \\

& \le 1 + \log ((\texttt{n}-1)/2+1) \\

& = 1 + \log ((\texttt{n}+1)/2) \\

& = \log (\texttt{n}+1) \enspace .
\end{align*}

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.

`n`

nodes has `n+1`

external nodes. The probability
of the random walk reaching the \(i\)th external node is exactly
\(p_i=1/2^{d_i}\), so the expected length of the random walk is given by
\begin{equation*}
H=\sum_{i=0}^{\texttt{n}} p_id_i
=\sum_{i=0}^{\texttt{n}} p_i\log\left(2^{d_i}\right)
= \sum_{i=0}^{\texttt{n}}p_i\log({1/p_i})
\end{equation*}
The right hand side of this equation is easily recognizable as the
entropy of a probability distribution over \(\texttt{n}+1\) elements. A basic
fact about the entropy of a distribution over \(\texttt{n}+1\) elements is that
it does not exceed \(\log(\texttt{n}+1)\), which proves the lemma.
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})\).

`h1`

and `h2`

are the roots of two heaps containing \(\texttt{n}_1\)
and \(\texttt{n}_2\) nodes, respectively, then the expected running time of
`merge(h1,h2)`

is at most \(O(\log \texttt{n})\), where \(\texttt{n}=\texttt{n}_1+\texttt{n}_2\).

`h1`

or the heap rooted at `h2`

.
The algorithm terminates when either of these two random walks fall out of its corresponding tree (when \(\texttt{h1}=\texttt{null}\) or \(\texttt{h2}=\texttt{null}\)). Therefore, the expected number of steps performed by the merge algorithm is at most \begin{equation*} \log (\texttt{n}_1+1) + \log (\texttt{n}_2+1) \le 2\log \texttt{n} \enspace . \end{equation*}

## 10.2.2 Summary

The following theorem summarizes the performance of a `MeldableHeap`

:

`MeldableHeap`

implements the (priority) `Queue`

interface.
A `MeldableHeap`

supports the operations `add(x)`

and `remove()`

in \(O(\log \texttt{n})\) expected time per operation.
# 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].

`BinaryHeap`

shown at the end of Figure 10.2.
`BinaryHeap`

shown at the end of Figure 10.3.
`remove(i)`

method, that removes the value stored in
`a[i]`

in a `BinaryHeap`

. This method should run in \(O(\log \texttt{n})\) time.
Next, explain why this method is not likely to be useful.
`i`

, determine the index of `i`

's
parent and each of `i`

's \(d\) children in this representation.
`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.
`MeldableHeap`

`h1`

shown in Figure 10.4. Use a coin to
simulate a random bit when needed.
`MeldableHeap`

`h1`

shown in Figure 10.4. Use a coin to
simulate a random bit when needed.
`remove(u)`

method, that removes the node `u`

from
a `MeldableHeap`

. This method should run in \(O(\log \texttt{n})\) expected time.
`BinaryHeap`

or
`MeldableHeap`

in constant time.
`BinaryHeap`

or
`MeldableHeap`

in \(O(k\log k)\) time. (Hint: Using another heap
might help.)
`k`

sorted lists, of total length `n`

. Using
a heap, show how to merge these into a single sorted list in \(O(n\log
k)\) time. (Hint: Starting with the case \(k=2\) can be instructive.)