Chapter 11: Priority Queues and Heaps

11.1The priority queue ADT

A data structure can be described at two levels: what it does (its operations, and what each changes and returns) and how it does it (the memory layout and the steps of each operation). A description at the first level is an abstract data type (ADT), and the priority queue is one. The same ADT can be implemented by very different data structures, and a main lesson of this chapter is how much that choice affects running time.

11.1.1What is a priority queue?

Picture a traffic jam. Cars move forward in the order they arrived, until an ambulance comes up behind with its siren on. Drivers pull aside and it passes them all, not because it arrived early but because its priority is high.

Computer systems are full of this pattern (Figure 11.1). An operating system runs the most important waiting process; a print queue can move an administrator's urgent job to the front; an event simulation handles the earliest event next. In each case the waiting items carry a priority, and the next item is chosen by it.

Note what the definition does not demand. A priority queue must answer only one question quickly, namely which item matters most right now; it need not keep its items sorted. That freedom is what makes efficient implementations possible.

Costs depend on the implementation. In an unsorted list, even looking at the top item means scanning everything, O(n). In a binary heap, looking takes O(1) and removing O(log n).

11.1.2Keys, values, and priorities

Each item has two parts: a key, which carries its priority, and a value, the data actually stored. In the emergency room, (1, "heart attack") and (4, "sprain") are two items; the first has key 1.

Which direction to use is a convention. Goodrich, Tamassia, and Goldwasser define the ADT as a min-priority queue with min() and removeMin(), and so do these notes, while most of the heap code uses a max-heap with insert and removeMax. The two differ only in the direction of comparison: change every < to > and a min-queue becomes a max-queue, so everything carries over.

The highest-priority item is the one at the “front”: the smallest key in a min-queue, the largest in a max-queue. If several items share that key, any of them counts as the front.

So in what order do equal-priority items leave? The ADT makes no promise. Nothing guarantees FIFO (first-in, first-out) order among equal keys; some implementations happen to preserve it, others don't, and Java's PriorityQueue gives no guarantee.

If ties must go by arrival, add an arrival number, taken from a counter, to the key. Comparison looks at the priority first and, on a tie, at the number, so the earlier item wins. Since the numbers are distinct, no two keys are ever equal and the order is fully determined.

11.1.3Queue or priority queue?

A small example shows the difference.

Alan arrived first but leaves the priority queue last. The relative order of Eve and Nina is the implementation's choice, not the ADT's; another implementation could send Nina out first.

A priority queue generalizes the ordinary queue: with arrival time as the key, a min-priority queue returns the oldest item, like a queue; with negated arrival time, it returns the newest, like a stack.

11.1.4Applications

A priority queue fits any problem of the form “repeatedly take the best of what is waiting.” Typical areas:

• Operating systems. The highest-priority process gets the CPU first: an interrupt handler before the user interface, the interface before a background backup.
• Graph algorithms. Dijkstra's shortest-path algorithm and A* search take the next closest node from a priority queue, keyed by its best known distance from the source.
• Emergency management. Triage and incident handling deal with the most urgent case first.
• Data compression. Huffman coding repeatedly merges the two lowest-frequency nodes, taking them with two removeMin calls and inserting the merged node back.

In all of these, items arrive over time and removals are interleaved with insertions. If all the data were known in advance, one sort would do. In Dijkstra's algorithm, though, each removal causes new insertions, and keeping a sorted array up to date after every insertion is expensive. Priority queues are built for exactly this.

11.1.5Operations and a Java interface

The min-priority queue ADT has the five operations in Table 11.2.

In Java, an ADT's contract is naturally an interface, which gives each operation's name, parameters, and return type but not its implementation:

public interface PriorityQueue<K, V> {
    void insert(K key, V value);
    Entry<K, V> min();        // null if empty
    Entry<K, V> removeMin();  // null if empty
    int size();
    boolean isEmpty();
}

K and V are the key and value types. Entry<K, V> is a small (key, value) pair type, returned by min() and removeMin() so that the caller gets the key too. The comments fix the empty-queue behavior: both methods return null. Some libraries throw an exception instead; either way, the choice is part of the contract that client code must know.

A max-priority queue calls these operations max() and removeMax(); the max-heap code in these notes uses insert and removeMax.

The interface says nothing about cost; that depends on the implementing class. An unsorted list, a sorted list, and a heap can all implement PriorityQueue<K, V>. Client code stays the same, and only the running time changes.

11.1.6A sequence of operations

Table 11.3 applies a sequence of operations to an empty min-priority queue. Contents are written as sets, since the ADT defines no internal order; items are listed by key for readability.

Note three things. min() and removeMin() return the same item, but only the latter removes it. (3,B) entered after (5,A) and (9,C) yet leaves first, and (7,D), inserted last, leaves before (9,C): the key decides. Finally, removeMin() on an empty queue returns null, as the contract says.

11.2List-based implementations

The simplest implementation keeps the items in a list, either unsorted, in arrival order, or always sorted by priority. Both work, but their costs are mirror images: one makes insertion cheap and removal expensive, the other the reverse. Comparing them in code shows why we need the binary heap.

11.2.1Unsorted and sorted lists

An unsorted list appends each new item without any comparisons, so insertion is O(1). Removal pays: the smallest key could be anywhere, so min and removeMin look at every item, O(n).

A sorted list keeps the items in key order, so the smallest is always at one end and min and removeMin take O(1). Now insertion pays: the new item's place must be found and items shifted, O(n) in the worst case.

Each implementation makes one operation fast and the other slow (Figure 11.2). Applications usually insert and remove about equally often, so the slow operation dominates, and n insertions plus n removals cost O(n²) either way. The binary heap balances the two at O(log n) each.

Which way to sort is an implementation choice. The figure puts the minimum first, but an array should keep it at the end: deleting the last cell of an array is cheap, as is deleting the first node of a linked list.

11.2.2Code trace: removeMin() on an unsorted array

In an array, the items occupy a[0] through a[n − 1]. Insertion is just a[n] = x; n++;, and removal looks like this:

// unsorted array: insert(x) { a[n] = x; n++; }  O(1)
public int removeMin() {        // requires n > 0
  int minIdx = 0;               // index of the minimum
  for (int k = 1; k < n; k++)
    if (a[k] < a[minIdx]) minIdx = k;
  int min = a[minIdx];
  a[minIdx] = a[n - 1];  n--;   // last item fills the gap
  return min;
}

The code first finds the minimum: minIdx holds the index of the smallest item seen so far, starting at 0, and the loop updates it whenever a[k] is smaller. It then saves that item in min.

Finally it closes the gap. With no order to preserve, there is no need to shift everything left; moving the last item into the gap and decrementing n is a single O(1) assignment. On a sorted array this trick would break the order.

Table 11.4 traces it on a = [5, 9, 3, 7, 4], n = 5.

Five items took 4 comparisons. In general the loop runs n − 1 times wherever the minimum is, since even a minimum in the first cell can't be confirmed until every item has been seen. So removeMin is Θ(n) in every case, and min() does the same scan without the final move.

The result, [5, 9, 4, 7], is unsorted, which is fine; but note that the move has rearranged it, carrying 4 from the end to the middle.

11.2.3Code trace: insert(4) on a sorted array

A sorted array must choose which end holds the minimum. At a[0], every removal shifts all the other items left, making removeMin O(n) and losing the sorted version's only advantage. So keep the array in decreasing order: the minimum is then at a[n − 1], and removing it just decrements n:

// sorted array: decreasing order, min always at a[n-1]
public void insert(int x) {
  int k = n - 1;
  while (k >= 0 && a[k] < x) {    // smaller than x
    a[k + 1] = a[k];              // shift one right
    k--;
  }
  a[k + 1] = x;  n++;
}
public int removeMin() { n--; return a[n]; }

insert searches from the back. While a[k] < x, the item a[k] belongs after x in decreasing order, so it shifts right to a[k + 1] and k decreases. The loop stops when k reaches −1 (x is the largest) or a[k] ≥ x; either way x goes at k + 1. The test k >= 0 comes first so that, by short-circuit evaluation of &&, a[−1] is never read.

Here is insert(4) on a = [9, 7, 5, 3, 2], n = 5.

Two items (2 and 3) shifted right. In between, the array briefly holds duplicates: after a[5] = a[4], 2 occupies two cells. That is not a bug. The extra copy is overwritten by 3 in the next step, and the leftover 3 is finally overwritten by 4. Shifting copies each item one cell right and needs fewer assignments than swapping.

The cost is proportional to the number of items shifted: none if the new item is the smallest, all n if it is the largest, and about n/2 on average, so insertion is O(n). removeMin() is one line and O(1), because the minimum is already at the end.

11.2.4Arrays versus linked lists

The sorted implementation can also use a linked list. The costs are similar but arise differently.

In an array, keeping the items sorted means shifting on insertion, O(n). The highest-priority item is kept at the end, so removal is O(1).

A linked list needs no shifting, but finding the new node's place still takes O(n), since a position can only be reached by walking from the head; linking the node in is then two O(1) assignments. Here the highest-priority item is kept at the head: deleting the head is one assignment, while deleting the tail of a singly linked list means finding the next-to-last node. Either way, the top item sits at the cheap end. The linked list pays in memory, since each node also stores a reference to the next.

The order of the two links matters. Doing prev.next = newNode first would destroy the only reference to 7, and the rest of the list would be lost. Link the new node to the rest of the list first, then the list to the new node.

11.2.5Code: a priority queue on a sorted array

Next, the sorted array becomes a general class whose items carry data and a priority. It is max-priority: larger priorities leave first. Each item is a small object:

class Item<T> {
    T data;
    int priority;
    Item(T v, int p) { data = v; priority = p; }
}

Item<T> is generic: data can be of any type, and priority is an integer. The queue keeps the items in an array:

// fields of SortedArrayPQ<E>
private Item<E>[] items =
    (Item<E>[]) new Item[10];
private int size = 0;
public boolean isEmpty() { return size == 0; }

The capacity starts at 10, and size counts the items. Java can't create generic arrays, so the code creates a raw Item array and casts it; the compiler's “unchecked cast” warning is harmless here because the array never leaves the class. Insertion:

public void insert(E data, int p) {
    if (size == items.length)
        items = Arrays.copyOf(items, 2 * size);
    int i = size;
    while (i > 0 && items[i-1].priority < p) {
        items[i] = items[i - 1];  // shift right
        i--;
    }
    items[i] = new Item<>(data, p);
    size++;
}

If the array is full, Arrays.copyOf makes one twice as large. Then i starts at the first empty cell, size, and moves left, shifting right every item whose priority is less than p. Where the loop stops, the new item goes. The largest priority thus sits at items[0], where removal takes it:

public E remove() {
    if (isEmpty()) return null;
    E result = items[0].data;
    for (int i = 1; i < size; i++)
        items[i - 1] = items[i];
    items[--size] = null;
    return result;
}

remove returns null on an empty queue; otherwise it takes the data from items[0] and shifts the rest left. Writing null into the vacated last cell drops a stale reference that would keep the removed object from being garbage-collected. items[--size] decrements size before indexing.

This class ignores the advice to keep the top item at the end. It sits at the front, so remove is O(n), as is insert in the worst case. The layout was chosen for readability; with the top at the end, remove would be one line.

The strict < in the loop matters too. An item of equal priority is not shifted, so the new item lands behind it. Equal-priority items therefore stay, and leave, in arrival order: the queue is FIFO on ties.

11.2.6Code trace: inserting with equal priority

After insert(A, 2), insert(B, 5), insert(C, 1), the array is [B:5, A:2, C:1] (cells written “data:priority”). Now insert(D, 5) is called. D ties with B: does it go in front of B or behind it?

public void insert(E data, int p) {
  if (size == items.length)
    items = Arrays.copyOf(items, 2 * size);
  int i = size;
  while (i > 0 && items[i-1].priority < p) {
    items[i] = items[i - 1];  // shift right
    i--;
  }
  items[i] = new Item<>(data, p);
  size++;
}

The key step is the comparison at i = 1: 5 < 5 is false, so B stays and D lands right behind it. Two remove() calls return B, then D, so arrival order is kept.

With <=, that comparison would be true, B would shift too, and D would go first: [D:5, B:5, A:2, C:1]. The array is still sorted, but the newcomer jumps ahead. One character turns FIFO ties into LIFO ties.

11.2.7Comparing the costs

Table 11.7 compares the two list implementations with the binary heap.

* By sorting the items first.   ** By bottom-up heap construction.

The last row covers building a queue from n items given at once. An unsorted list just copies them; a sorted list must sort them, O(n log n); and a heap can be built in place in O(n) by a special algorithm instead of n insertions.

What usually matters is the total cost of a sequence. Suppose we insert n items into an empty queue and then call removeMin n times.

• Unsorted list: n · O(1) + n · O(n) = O(n²). Insertions are cheap, but each removal scans what remains.
• Sorted list: n · O(n) + n · O(1) = O(n²). Now the insertions are expensive.
• Binary heap: 2n · O(log n) = O(n log n).

For n = 10⁶, n² = 10¹² while n log₂ n ≈ 10⁶ · 19.93 ≈ 2 · 10⁷, a ratio of n / log₂ n ≈ 50,000. A job a heap finishes in one second would take a list about 50,000 seconds, roughly fourteen hours. Asymptotic analysis predicts gaps like this in advance.

11.3Binary heaps

The list implementations are two extremes: the unsorted list keeps no order, so insertion is free; the sorted list keeps full order, so removal is free. The binary heap keeps a partial order, strong enough to hold the top item in a fixed place, loose enough that each operation moves only a few items.

11.3.1Two properties

The binary heap is the most common way to implement a priority queue. Its items sit in the nodes of a binary tree that satisfies two conditions.

In Figure 11.7, the root 9 has children 7 and 8; 7 has children 3 and 5, and 8 has one child, 6. Every parent exceeds its children (9 ≥ 7, 8; 7 ≥ 3, 5; 8 ≥ 6), and the last level's only gap is at the far right.

Heap order is a local rule about parents and children, but chained down the tree it says that every node is at least as large as everything in its subtree. The root's subtree is the whole tree, so the largest key is at the root, and peeking at the top item takes O(1).

The rule says nothing about siblings: swap 7 and 8 in Figure 11.7 and the tree is still a heap. So a heap is not sorted; apart from the root, a node's position doesn't tell you its rank.

The second property fixes the shape. A complete binary tree is the shortest binary tree with its number of nodes, so its height is ⌊log₂ n⌋, and it can be stored in an array with no gaps and no pointers.

Together, the two properties make heap operations fast. Insertion and removal work along one path between the root and a leaf, no longer than the height, so both take O(log n).

11.3.2Min-heaps and max-heaps

Min-heaps and max-heaps differ in the direction of the inequality. In a min-heap, key(parent) ≤ key(child); the smallest key is at the root, and the heap implements a min-priority queue. In a max-heap, key(parent) ≥ key(child), and the root holds the largest key.

In the min-heap of Figure 11.8, the siblings 7 and 3 have 7 > 3, which is fine: order holds only between parent and child. 7 even exceeds 5 and 6, the children of 3; nodes on different branches need not be related.

Geometrically, heap order says every root-to-leaf path is sorted: increasing in a min-heap, decreasing in a max-heap, as with 9 → 3 → 2, 9 → 3 → 1, 9 → 6 → 5, and 9 → 6 → 4 in the figure. A heap is a bundle of sorted paths joined at the root, and insertion and removal each repair just one of them.

11.3.3Complete binary trees and height

A complete tree is easily confused with a perfect one. The difference is the last level, which in a complete tree need not be full, only packed from the left without gaps. Figure 11.9 compares three trees.

In the left tree, root 1 has children 2 and 3, and 4 and 5 hang under 2, leaving the space under 3 empty; the tree is complete. In the middle tree, 2 lacks a right child while 3 has a left one, leaving a gap. In the right tree, both last-level nodes are under 3 and the positions under 2 are empty. Neither of these two can be a heap.

Two checks: for n = 7, log₂ 7 ≈ 2.81 and h = 2, since a root, two children, and four grandchildren fill three levels. For n = 1000, 2⁹ = 512 ≤ 1000 < 1024 = 2¹⁰, so h = 9: a thousand-item heap has root-to-leaf paths of only 9 edges, and a million items need just 19. Multiplying the number of items by a thousand adds only 10 steps.

Completeness also means a new node's place is never in doubt: the leftmost free spot on the last level, or the far left of a new level if the last one is full. In the array this is exactly index n. Likewise, the only node that can be removed without spoiling the shape is the rightmost on the last level, the array's last element.

11.3.4Heap or not?

To decide whether a tree is a heap, check the two properties separately: is the shape complete, and does every parent–child pair satisfy the inequality in the same direction?

Tree (d) shows that heap order alone is not enough. A bad shape leaves gaps in the array: (d) must be stored as [10, 8, 9, _, _, 7, 6]. The index formulas and the rule “a new item goes at index n” both assume there are no gaps.

11.3.5Code trace: isHeap()

Checking whether an array is a max-heap is easy. An array has no gaps, so the tree it represents is automatically complete, and only heap order needs checking. The node at index i has its parent at (i − 1) / 2 (Definition 11.5).

static boolean isHeap(int[] a) {  // max-heap?
  for (int i = 1; i < a.length; i++) {
    int p = (i - 1) / 2;           // parent
    if (a[p] < a[i]) return false; // order violated
  }
  return true;
}

The loop visits each non-root node, i = 1 to n − 1, and compares it with its parent. A parent smaller than its child violates the order, and the method returns false at once; if the loop finishes, the array is a max-heap.

Every node has exactly one parent, so each pair is checked exactly once. Looping over children is also simpler than looping over parents, since there is no need to ask whether a right child exists.

Here is the trace on a = [10, 8, 9, 3, 5, 7, 4, 6].

The first seven items, [10, 8, 9, 3, 5, 7, 4], form a valid max-heap, and on them the method returns true in Java. The appended 6 exceeds its parent 3. This is why insertion needs a repair step: writing the new item at the end keeps the shape but not necessarily the order.

In the worst case, when the array is a heap, the loop makes n − 1 comparisons: O(n) time and O(1) extra space. No check can be faster, since any skipped pair might hide a violation.

For empty and one-element arrays the loop never runs and the method returns true, correctly: with no parent–child pairs, heap order holds trivially. For a min-heap, reverse the test: if (a[p] > a[i]) return false;.

11.3.6The array representation

Trees are usually built from node objects and references, but a heap needs neither. Its nodes are written into an array in level order, level by level and left to right: the root in heap[0], its children in heap[1] and heap[2], the grandchildren in heap[3] through heap[6], and so on.

Because the tree is complete, level order leaves no gaps (Figure 11.12): n items fill exactly heap[0] through heap[n − 1], and parent and child links are computed from the indices rather than stored.

This has three practical advantages. It saves memory, since no child references are stored. It is fast, since contiguous cells reach the processor's cache in blocks, and walking an array beats chasing scattered nodes. And it is simple: the last item and the first free position are both given by one counter, n.

These notes index from 0, with the root at heap[0]. Some books start at 1; the two are equivalent, with slightly different formulas.

11.3.7Parent and child indices

In level order, a node's children and parent follow from simple formulas.

To see why, note that level d starts at index 2^d − 1 (0, 1, 3, 7, …). Since each node takes two children in turn, the children of a level's jth node (counting from 0) are the 2jth and (2j + 1)th nodes of the next level. In indices, the node is i = 2^d − 1 + j and its left child is 2^d+1 − 1 + 2j = 2(2^d − 1 + j) + 1 = 2i + 1; the right child is the next cell. The parent formula inverts this: subtracting 1 from 2i + 1 or 2i + 2 and halving, rounded down, gives i.

Java's integer division rounds positive numbers down, so the parent is simply (i - 1) / 2 in code, and the child formulas need only addition and multiplication. Moving to a neighbor in a heap costs no more than following a reference.

1-based representation. Some books leave heap[0] empty and put the root at heap[1]; then node k has children 2k and 2k + 1 and parent ⌊k/2⌋. The formulas are shorter at the cost of one cell. Either works, as long as you use one consistently.

11.4Insertion and removal

Both basic heap operations follow one pattern. First they preserve the shape, putting the item into, or taking it from, the one place where completeness survives. This may break heap order at one spot, and the second step repairs it by moving the item up or down a single path: up-heap or down-heap. The code in this section is for a max-heap.

11.4.1Insertion: up-heap

Insertion into a max-heap takes three steps:

1. Preserve the shape. Write the item into the first free position, heap[n], and increment n.
2. Find the defect. Order can now fail only between the new item and its parent. If the item is larger, swap them.
3. Repeat with the new parent, until the item reaches the root or its parent is at least as large.

In Figure 11.14, 10 enters at index 6 as the right child of 8. Since 8 < 10, they swap and 10 moves to index 2; since the root 9 < 10, they swap again. 10 is now the root, and the result is [10, 7, 9, 3, 5, 6, 8].

The operation goes by many names (up-heap, bubble-up, sift-up, swim). Our code calls it swim: a large key rises toward the root like a buoyant object swimming to the surface.

In short, the parent that moves down was already at least as large as its other child, so fixing the defect above never creates one below.

11.4.2Code: insert() and swim()

The max-heap class keeps an int array and a counter:

public class MaxHeap {
  private int[] heap = new int[4];
  private int n = 0;                // number of items

public void insert(int x) {
  if (n == heap.length) resize(2 * heap.length);
  heap[n] = x;  n++;              // first free position
  swim(n - 1);
}
private void swim(int i) {        // up-heap
  while (i > 0) {
    int parent = (i - 1) / 2;
    if (heap[parent] >= heap[i]) return;
    swap(i, parent);  i = parent;
  }
}
private void swap(int a, int b) {
  int t = heap[a];  heap[a] = heap[b];  heap[b] = t;
}
}  // MaxHeap

The capacity starts at 4. insert doubles it with resize if the array is full (n == heap.length), writes x into heap[n], increments n, and calls swim on the new index, n − 1.

swim(i) loops while i is not the root, computing the parent's index as (i − 1) / 2. If the parent is at least as large, the order holds and the method returns; otherwise swap, a three-assignment helper with a temporary variable, exchanges the two cells, and i moves up to the parent.

The loop exits in two ways: through the while test when i = 0 (the root has no parent), or through the inner return when the parent is ≥ the item, since the path above is already in order. Using >= avoids pointless swaps of equal keys.

Cost: swim makes at most ⌊log₂ n⌋ constant-time passes, O(log n). Apart from resize, insert does constant work, and the rare resizes cost amortized O(1) per insertion. Insertion is thus amortized O(log n).

11.4.3Code trace: insert(10), insert(8)

The heap starts as [9, 3, 6, 2, 1, 5, 4], with n = 7 and capacity 16; the largest item, 9, is at the root. We call insert(10), then insert(8).

insert(10) is the worst case: the new item is the largest and climbs from leaf to root in 3 swaps, the height ⌊log₂ 8⌋ = 3. insert(8) stops halfway: after swapping with 3, it meets 9 ≥ 8 and returns. That makes 4 swaps in all.

Note that the first parent compared in insert(8) is the 3 that insert(10) pushed from index 1 down to index 3. Each up-heap pushes the items on its path down a level, and later insertions work on the rearranged heap.

11.4.4Filling an empty heap

To build a heap from scratch, insert 4, 5, 2, 6, 1, 3 into an empty max-heap of capacity 4 (Table 11.10).

The first item simply becomes the root. insert(6) brings the largest item so far, which climbs to the root. At insert(1) the array is full (n = 4 = heap.length), so the capacity grows to 8 first; 1 is smaller than its parent 5 and stays put. Finally, 3 swaps with its parent 2 and settles under 6.

The result, [6, 5, 3, 4, 1, 2], is not sorted but is a valid max-heap: 6 ≥ 5, 3; 5 ≥ 4, 1; 3 ≥ 2. Another insertion order could give another heap: the shape is fixed, but where the items land depends on the order of insertion.

11.4.5Growing the capacity

A Java array can't change length, so growing the capacity means allocating a larger array and copying:

private void resize(int capacity) {
  int[] newArr = new int[capacity];
  for (int k = 0; k < n; k++)
    newArr[k] = heap[k];        // copy
  heap = newArr;                // old array becomes garbage
}

resize(capacity) allocates the new array, which Java fills with zeros, copies the first n items to the same indices, and points heap at the new array. The old array is no longer referenced, and the garbage collector reclaims it.

One resize costs O(n), but resizes are rare. With doubling, they happen at 4, 8, 16, … items, so n insertions copy 4 + 8 + 16 + … items, a sum whose last term is below n. Since each term doubles the one before, the sum is less than twice the last term, under 2n in all: a constant per insertion, so resizing is amortized O(1).

Growing by a fixed amount, say 4 cells, would be a bad choice: a resize every 4 insertions copies 4 + 8 + 12 + … ≈ n²/8 items, O(n) per insertion.

Removal can shrink the array symmetrically, halving it when it falls to a quarter full. Why a quarter rather than a half? At a half, alternating insertions and removals at the threshold would resize every time. Shrinking is optional and is omitted here.

11.4.6Removing the maximum: down-heap

The largest item of a max-heap is at the root. Removing it also has two phases.

1. Save the root. It is the return value.
2. Preserve the shape. Only the last node can leave without spoiling completeness, so move heap[n − 1] to the root and decrement n.
3. Repair. The new root is probably small and may be smaller than its children. Swap it with the larger child.
4. Repeat until it reaches a leaf or is at least as large as both children.

In Figure 11.18, 4 replaces the removed 9 at the root. Its children are 7 and 8, and it swaps with the larger, 8. At index 2 its only child is 6, and 4 < 6, so it swaps again and reaches a leaf. The result is [8, 7, 6, 3, 5, 4].

Why the larger child? The child that moves up becomes the parent of its sibling. If it is the larger one, order holds at the new root; if the smaller moved up, it would sit above a larger child, and the defect would merely move. In a min-heap the same argument picks the smaller child.

Cost: two comparisons per level, one to pick the larger child and one against the item, over at most h = ⌊log₂ n⌋ levels, for O(log n) in total.

11.4.7Code: removeMax() and sink()

public int removeMax() {        // requires n > 0
  int max = heap[0];
  swap(0, n - 1);  n--;         // last item to the root
  sink(0);
  return max;
}
private void sink(int i) {        // down-heap
  while (2 * i + 1 < n) {       // left child exists?
    int j = 2 * i + 1;            // j: larger child
    if (j + 1 < n && heap[j + 1] > heap[j]) j++;
    if (heap[i] >= heap[j]) return;
    swap(i, j);  i = j;           // down one level
  }
}

removeMax saves the root in max, swaps it with the last item, and decrements n. The swap also leaves the old root at the end of the array, outside the heap, which heap sort exploits: repeated removals collect the largest items at the end. Then sink(0) runs and max is returned. A real class would also check if (n == 0) and throw an exception, since heap[0] means nothing in an empty heap.

sink(i), named for an object sinking in water, is down-heap. The loop test 2 * i + 1 < n asks whether i has a left child; in a complete tree a node without one has no right child either, so the loop ends at a leaf. Inside, j starts at the left child and moves to the right one if it exists and is larger. If the item is at least as large as child j, the method returns; otherwise they swap and the item drops a level.

The test j + 1 < n is critical. After removeMax, the old root still sits at index n; without the test, heap[j + 1] could read it, take it for the larger child, and move it back into the heap (Example 11.5).

11.4.8Code trace: removeMax()

Call removeMax() on [9, 3, 6, 2, 1, 5, 4] (n = 7).

In pass 1 the root's larger child is 6. In pass 2, the 4 at index 2 has only a left child, j = 5; the right candidate, 6, is not less than n = 6. heap[6] still holds 9, but the j + 1 < n test keeps it from being read. In all, 3 comparisons and 2 swaps; with height ⌊log₂ 6⌋ = 2, no more swaps are possible.

11.4.9Code trace: two removeMax() calls in a row

Next, remove the maximum twice from [10, 9, 6, 8, 1, 5, 4, 2, 3], the heap left by the up-heap trace.

The removals return 10 and 9. The first sinking item, 3, stops above a leaf: at index 3 its only child is 2. The second, 2, sinks all the way. The last two cells now hold 9 and 10, [8, 3, 6, 2, 1, 5, 4 | 9, 10]: removed items pile up at the end, decreasing from right to left.

11.4.10insert and removeMin on a min-heap

A min-heap works the same way with the comparisons reversed: up-heap moves an item up while it is smaller than its parent, and down-heap swaps it with the smaller child. Start from the min-heap [2, 5, 3, 9, 6, 8, 4].

Here the insertion and removal cancel out exactly, but that is a coincidence: the inserted item was the smallest and pushed its whole path down a level, and the 9 then sank back along the same path. In general, an insertion followed by a removal does not restore the original heap.

To turn max-heap code into min-heap code, reverse three comparisons: heap[parent] <= heap[i] instead of >= in swim, and in sink the smaller child instead of the larger, with heap[i] <= heap[j] as the stopping test. Alternatively, store negated keys in a max-heap: the largest −x is the smallest x.

11.4.11The cost of heap operations

* Amortized, including growing and shrinking the array.

The height formula makes this concrete: a heap of n = 10⁶ items has height ⌊log₂ 10⁶⌋ = 19, so an insertion or removal makes at most 19 swaps, where a sorted array might shift half a million items.

Memory is O(n), and doubling leaves at most half the array empty. A linked tree would instead store two child references, and often a parent reference, in every node.

The last row of the table is a reminder: a heap finds only the top item quickly. “Is 7 in the queue?” requires a full scan, and changing or removing a particular item requires finding it first. The adaptable priority queue addresses this.

11.4.12Adaptable priority queues

Sometimes an item's priority changes while it waits. In Dijkstra's algorithm, a shorter path to a node lowers its distance, which is its key; in an emergency room, a waiting patient gets worse. And sometimes an item leaves early: a patient gives up, a process is canceled.

The hard part is knowing where e is in the heap array, since searching an unsorted heap takes O(n). Goodrich and his coauthors use a location-aware entry: each item object stores its current index alongside its key and value, and every swap updates the indices of both items.

With the location known, both operations use familiar tools:

• replaceKey(e, k). Change the key of heap[e.index]. In a max-heap, a larger key can conflict only with the parent, so apply up-heap; a smaller key only with the children, so apply down-heap.
• remove(e). Swap the item with the last one and decrement n. The replacement may be larger than its parent or smaller than its children, so apply up-heap or down-heap as needed.

Without the location field, each operation would start with an O(n) search; with it, the item is reached in O(1) and the operation costs O(log n). The price is updating two indices per swap, a constant overhead.

11.4.13Code trace: increasing and decreasing a key

Our simple max-heap stores integers rather than item objects, so an item is identified by its index: changeKey(i, key) sets heap[i] to key and repairs the order.

public void changeKey(int i, int key) {
  int old = heap[i];
  heap[i] = key;
  if (key > old) swim(i);      // increased: up
  else sink(i);                // decreased: down
}
private void swim(int i) {       // up-heap
  while (i > 0) {
    int parent = (i - 1) / 2;
    if (heap[parent] >= heap[i]) return;
    swap(i, parent);  i = parent;
  }
}

The method saves the old value, writes the new one, and picks a direction: swim(i) if the key grew, sink(i) otherwise. For an unchanged key, sink returns at once, since the item already dominates its children. The shape never changes; only values along one path move.

Increasing a key. Call changeKey(4, 8) on [9, 3, 6, 2, 1, 5, 4].

8 rose one level, stopping below the root, and only the path 4 → 1 → 0 was examined. As in the proof, the 3 that moved down lands in a leaf, and at index 1 it already exceeded its other child, 2.

Decreasing a key. Now decrease the root of the updated heap [9, 8, 6, 2, 3, 5, 4]: changeKey(0, 1).

1 sank two levels and 8 rose to the root. Decreasing the root's key and calling sink(0) is exactly the down-heap of removeMax, except that the value at the root is the user's new key rather than the last item.

Either way the cost is bounded by the path length, O(log n); without the index, finding the item would raise it to O(n).

11.5Building a heap and heap sort

So far, items have entered the heap one at a time. When all of them are available up front (numbers read from a file, tasks waiting in an array), a faster method rearranges the array in place. It is also the first step of heap sort.

11.5.1Two ways to build a heap from n items

Method 1: n insertions. Insert the items one by one, each with an O(log n) up-heap, for O(n log n) in total. When items arrive over time and the input can't be seen in advance (the online case), this is the only option.

Method 2: bottom-up construction. An array holding all the items already is a complete binary tree; only heap order is missing. Establish it by applying down-heap to each node from the last internal node back to the root:

for (int k = n / 2 - 1; k >= 0; k--)   // last internal node to root
    sink(k);                             // subtrees are heaps; sink k

The loop starts at ⌊n/2⌋ − 1, the last node with a child; every later index is a leaf, since 2i + 1 ≥ n for i ≥ ⌊n/2⌋. Leaves are already heaps, so half the array is never touched.

Correctness rests on the loop's direction. When sink(k) is called, both subtrees of k are already heaps, because their roots have larger indices and were processed earlier or are leaves. That is exactly the situation down-heap repairs, so when the loop reaches the root, the whole tree is a heap.

11.5.2Code trace: buildHeap()

Added to the max-heap class, bottom-up construction turns the n items in the array into a heap:

public void buildHeap() {       // arbitrary array
  for (int k = n / 2 - 1; k >= 0; k--)
    sink(k);                    // subtrees are heaps
}
private void sink(int i) {        // down-heap
  while (2 * i + 1 < n) {       // left child exists?
    int j = 2 * i + 1;            // j: larger child
    if (j + 1 < n && heap[j + 1] > heap[j]) j++;
    if (heap[i] >= heap[j]) return;
    swap(i, j);  i = j;           // down one level
  }
}

The input is the classic example from Cormen and his coauthors: [4, 1, 3, 2, 16, 9, 10, 14, 8, 7], n = 10. It is not a heap; the root, 4, is smaller than the 16 below it, for instance. Indices 5 through 9 are leaves, so the loop starts at k = 10/2 − 1 = 4.

There were seven swaps. Upper nodes traveled farther (the 4 at k = 0 sank three levels) but are few; lower nodes were leaves or made at most one swap. That balance keeps the total linear.

11.5.3Why is bottom-up construction O(n)?

At first sight, bottom-up construction costs O(n log n): about n/2 down-heaps of up to O(log n) each. That bound is true but loose. A down-heap costs at most the node's height, its distance to the deepest leaf below it, and most nodes are near the bottom, where heights are small.

Take a perfect binary tree of 15 nodes (all levels full, height 3).

Over half the nodes are leaves and do nothing, and only a few high nodes do much. The 11 swaps are fewer than the 15 nodes; a Java run on the worst input for a max-heap, 1 to 15 in increasing order, also counts exactly 11.

Building the same tree by 15 insertions costs far more, because up-heap costs depend on depth, the distance from the root, and most nodes are deep. With increasing input, every item climbs to the root: 2 nodes at depth 1, 4 at depth 2, and 8 at depth 3 make 0 + 2 · 1 + 4 · 2 + 8 · 3 = 34 swaps, the count Java gives too.

To sum the series, let S = 1/4 + 2/8 + 3/16 + …. Then S/2 = 1/8 + 2/16 + … and S − S/2 = 1/4 + 1/8 + 1/16 + … = 1/2, so S = 1.

In a sentence: down-heap costs depend on height and up-heap costs on depth, and most nodes are low, with small height and large depth. Bottom-up construction works in the cheap direction.

11.5.4Heap sort

A heap also yields a sorting algorithm. Repeatedly removing the maximum produces the items in decreasing order, and since removeMax parks each removed root just past the end of the heap, they collect at the end of the same array.

Heap sort has two phases:

1. Build the heap bottom-up: O(n).
2. Move the largest to the end, n − 1 times. Swap the root with the heap's last item, shrink the heap by one, and down-heap from the root: O(log n) per round, O(n log n) in total.

Mid-run (Figure 11.25), the array has two parts: a max-heap in front, shrinking by one each round, and a sorted part behind, growing by one. Every sorted item is at least as large as everything in the heap, so it is in its final place, and no extra array is needed.

Heap sort has four notable properties:

• In place. The heap lives in the array being sorted, so extra memory is O(1).
• O(n log n) in the worst case. Quick sort is very fast on average but degrades to O(n²) with bad pivots; heap sort has no bad case.
• Not stable. Long-distance swaps between the root and the end can reorder equal keys.
• Direction. A max-heap sorts in increasing order, since the largest item goes last; a min-heap sorts in decreasing order.

11.5.5Code: heapSort()

public static void heapSort(int[] a) {
  int n = a.length;
  // 1) build: from the last internal node to the root
  for (int k = n / 2 - 1; k >= 0; k--)
    sink(a, k, n);
  // 2) sort: move the largest to the end
  for (int last = n - 1; last > 0; last--) {
    swap(a, 0, last);
    sink(a, 0, last);           // heap size = last
  }
}
static void sink(int[] a, int i, int n) {
  while (2 * i + 1 < n) {
    int j = 2 * i + 1;
    if (j + 1 < n && a[j + 1] > a[j]) j++;
    if (a[i] >= a[j]) return;
    swap(a, i, j);  i = j;
  }
}

These are standalone static methods. This sink takes the array, an index, and the current heap size in place of the heap and n fields, but is otherwise the class's sink. The size must be a parameter because the heap shrinks each round while the array does not.

The first loop is bottom-up construction. In the second, last indexes the heap's last item. Each round swaps the root with a[last], fixing the largest item in place, and calls sink(a, 0, last): the new heap size is last, so sink ignores index last and beyond. The final round has last = 1; a one-item heap needs no work.

The helper swap(a, i, j) exchanges two cells:

static void swap(int[] a, int i, int j) {
  int t = a[i];  a[i] = a[j];  a[j] = t;
}

Heap sort turns the classic array {4, 1, 3, 2, 16, 9, 10, 14, 8, 7} into {1, 2, 3, 4, 7, 8, 9, 10, 14, 16}; Table 11.20 shows each round of the second phase.

11.5.6Code trace: heapSort([6, 5, 3, 4, 1, 2])

A smaller input shows each sink call of the second phase: a = [6, 5, 3, 4, 1, 2].

Phase 1. sink runs for k = 2, 1, 0, but the array is already a max-heap (6 ≥ 5, 3; 5 ≥ 4, 1; 3 ≥ 2), so no swaps are made.

Each round moves one cell from the heap to the sorted part. Besides the 5 root swaps, sink made 6 swaps, going two levels deep early on and less as the heap shrank. The total is at most log₂ n + log₂(n − 1) + … ≤ n log₂ n, so O(n log n).

11.5.7Sorting with a priority queue

Heap sort is a special case of a general idea: any priority queue can sort, by inserting everything and then calling removeMin n times. The algorithm you get, and its running time, depend on the implementation.

With an unsorted list, each removeMin selects the smallest remaining item: selection sort. With a sorted list, each insert puts the item in place within the sorted part: insertion sort. A heap balances the two phases.

This is the distinction between ADT and data structure in miniature: the algorithm (“insert everything, then remove everything”) never changes, yet changing the implementation cuts the time from O(n²) to O(n log n).

11.5.8Other kinds of heaps

Other heaps suit other mixes of operations.

In a d-ary heap, a complete tree whose nodes have up to d children, the 0-based array formulas give node i children di + 1 through di + d and parent ⌊(i − 1)/d⌋. In a 3-ary heap, index 7 has parent ⌊6/3⌋ = 2, whose children are 7, 8, and 9.

Its height is log_d n, shrinking as d grows. Up-heap makes one comparison per level, so insertion speeds up to O(log_d n), but down-heap must find the largest of d children per level, so removal costs O(d log_d n). With many insertions and key decreases but few removals, as in Dijkstra's algorithm on dense graphs, a d-ary heap can beat a binary one.

Binomial and Fibonacci heaps are forests rather than single trees, designed chiefly to speed up merging two queues and decreasing keys. Fibonacci heaps appear in the theoretically fastest versions of Dijkstra's and Prim's algorithms.

Merging binary heaps costs O(n): concatenate the arrays and rebuild bottom-up. Despite the Fibonacci heap's theoretical edge, the binary heap usually wins in practice, thanks to simple code, small constants, and a cache-friendly array. Java's PriorityQueue and Python's heapq both use one.

11.6Java and applications

Writing a heap yourself is the best way to understand it, but real programs usually use the built-in class, java.util.PriorityQueue in Java. This section covers its use, its internals, and typical applications of heaps.

11.6.1Java's built-in PriorityQueue

PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.offer(5); pq.offer(1); pq.offer(8);
pq.peek();   // 1  (min-heap, O(1))
pq.poll();   // 1  (O(log n))

// reversed comparator for a max-heap
PriorityQueue<Integer> maxPq =
    new PriorityQueue<>(Comparator.reverseOrder());

// patients: smaller priority first
PriorityQueue<Patient> er = new PriorityQueue<>(
    Comparator.comparingInt(p -> p.priority));

PriorityQueue<Integer> is a min-heap by default: it orders items naturally and keeps the smallest in front. offer inserts, peek looks at the front item, and poll removes it. After three offer calls, peek() returns 1 without changing the queue, and poll() returns 1 and removes it. On an empty queue these two return null, while their counterparts add, element, and remove throw an exception.

A Comparator passed to the constructor changes the ordering. Comparator.reverseOrder() makes the queue act as a max-heap: with the same 5, 1, 8, peek() returns 8. For our own classes, an expression like Comparator.comparingInt(p -> p.priority) names the field to compare. If Alan (3), Eve (1), Carl (2), and Nina (1) enter the er queue and are removed in turn, the two priority-1 patients leave first, then Carl, then Alan.

Four facts about the class are worth knowing:

• Structure. An array-based binary min-heap whose array grows automatically.
• Costs. offer and poll are O(log n); peek and size are O(1); remove(object) and contains are O(n), since they search the array linearly.
• Concurrency. The class is not thread-safe; when threads share a queue, use PriorityBlockingQueue.
• Ties. Equal priorities have no FIFO guarantee. Eve leaving before Nina is an accident of this input; another insertion order could reverse them.

11.6.2Code trace: what PriorityQueue does inside

The program below shows the class from outside; the trace shows its internal array (named queue in the Java source) at each step.

PriorityQueue<Integer> pq =
    new PriorityQueue<>();        // min-heap
pq.offer(5);
pq.offer(1);
pq.offer(8);
System.out.println(pq.peek());    // looks
System.out.println(pq.poll());    // removes
System.out.println(pq.poll());
System.out.println(pq.size());

The program prints 1 (peek), 1 and 5 (poll twice), and 1 (size). Java's siftUp and siftDown are min-heap versions of our swim and sink, generalized to work with any Comparator.

Printing a PriorityQueue shows its internal array, not a sorted list: inserting 3, 1, 2 prints [1, 3, 2]. A for-each loop visits the same internal order. Only repeated poll calls yield the items in sorted order.

11.6.3The kth largest element

Finding the kth largest element is a common task: the third-highest exam grade, the tenth-busiest hour on a server. Sorting works but takes O(n log n) and keeps all n items in memory. A min-heap of at most k items does better:

static int kthLargest(int[] a, int k) {
  PriorityQueue<Integer> pq = new PriorityQueue<>();
  for (int x : a) {
    pq.offer(x);                    // O(log k)
    if (pq.size() > k) pq.poll();  // drop the smallest
  }
  return pq.peek();       // smallest of the k largest
}

The invariant: after each step, the heap holds the k largest items seen so far, with the smallest of them at the root. Each new item is added, and if the heap reaches k + 1 items its minimum is dropped, since an item with k larger ones can't be among the k largest. At the end, the root is the smallest of the k largest: the kth largest.

Here is kthLargest([5, 1, 9, 3, 7, 6], 3).

The dropped items, 1, 3, and 5, are all outside the top three; sorted, the array is [1, 3, 5, 6, 7, 9], and the third largest is indeed 6.

Cost: with at most k + 1 items in the heap, each offer and poll is O(log k), for O(n log k) time and O(k) extra memory, much better than sorting when k is small. The memory saving matters too: items streaming from a file or network need not all be stored.

11.6.4Merging k sorted lists

Heaps also merge k sorted lists into one, as in external sorting, which sorts a large file in pieces and then merges them. Let N be the total number of items.

Put the first item of each list into a min-heap, each tagged with its list. Then, until the heap is empty, remove the minimum, output it, and insert the next item of its list, if any. The heap never holds more than one item per list, so at most k.

Each item enters and leaves the heap once, at O(log k) per operation, so the total is O(N log k), against O(N log N) for gathering everything into one array and sorting.

11.6.5A priority scheduler

An operating system's scheduler decides which waiting process gets the CPU next. In priority scheduling each process has a priority level, and a common design keeps one FIFO queue per level.

• Strict priority. The CPU always takes the front process of the highest non-empty queue. In Figure 11.30, P4 runs first; once the high level is empty, P1 and P5 get their turn.
• FIFO within a level. Equal-priority processes run in arrival order. If each runs for a time slice (quantum) and then rejoins the back of its queue, the level is scheduled round robin.
• Starvation and aging. If high-priority processes keep arriving, low-priority ones may never run: starvation. The usual cure is aging, raising a waiting process's priority step by step until it reaches the upper levels and runs.

With few levels, one queue per level is simplest and fastest, since finding the highest non-empty level takes constant time. With a wide range of priorities (say, a deadline per process), a single heap is used instead, with (priority, arrival number) keys to keep ties FIFO. Aging then becomes a key change, O(log n) in an adaptable priority queue.

11.7Common mistakes

The table collects the most frequent mistakes from this chapter; use it as a checklist when reviewing heap code.

Most of these bugs hide in small tests: the right-child bug appears only at certain sizes, the tie bug only with equal keys. To test a heap reliably, check the array with isHeap after every operation and compare results against a library class such as PriorityQueue on random inputs.

11.8Summary

• A priority queue is an ADT whose items leave by priority, not arrival. Items are (key, value) pairs; the operations are insert, min, removeMin, size, and isEmpty (max and removeMax in a max-queue). Equal keys have no FIFO guarantee; add an arrival number if needed.
• List-based implementations: an unsorted list inserts in O(1) and removes in O(n), a sorted list the reverse; either way n insertions and removals take O(n²). Keep the top item at the end of a sorted array, at the head of a linked list.
• A binary heap satisfies heap order (parent ≥ child in a max-heap) and completeness. The top item is at the root, and the height is ⌊log₂ n⌋. A heap is neither sorted nor a binary search tree.
• The array representation stores nodes in level order, without gaps or references. With 0-based indices, the children are 2i + 1 and 2i + 2, the parent ⌊(i − 1)/2⌋.
• Insertion writes to heap[n] and applies up-heap; removeMax moves the last item to the root and applies down-heap toward the larger child. Both are O(log n). Down-heap must test j + 1 < n for the right child. Doubling the capacity makes resizing amortized O(1).
• An adaptable priority queue adds replaceKey and remove; if items know their array positions, each takes one up-heap or down-heap, O(log n).
• Bottom-up construction applies down-heap from the last internal node (⌊n/2⌋ − 1) to the root in O(n), because down-heap costs depend on height and most nodes are low; n insertions take O(n log n).
• Heap sort builds a heap, then n − 1 times moves the root to the end and shrinks the heap: in place, O(n log n) in the worst case, not stable. Sorting with a priority queue gives selection sort on an unsorted list and insertion sort on a sorted one.
• Java's PriorityQueue is an array-based binary min-heap; pass Comparator.reverseOrder() for a max-heap. A size-k min-heap finds the kth largest element in O(n log k) and merges k sorted lists in O(N log k).

11.9Key terms

Each term links to the course glossary, which gives its Turkish equivalent and its use in other chapters.

• priority queue
• abstract data type (ADT)
• key
• value
• queue
• FIFO
• interface
• generic
• binary heap
• heap
• max-heap
• min-heap
• complete binary tree
• perfect binary tree
• root
• leaf
• internal node
• parent
• child
• sibling
• level
• level order
• height
• depth
• up-heap
• down-heap
• swap
• capacity
• dynamic array
• amortized analysis
• adaptable priority queue
• bottom-up heap construction
• heap sort
• in-place
• stable sort
• selection sort
• insertion sort
• quick sort
• round robin
• aging

11.10Test Yourself

1. An empty min-priority queue receives insert(7, a), insert(2, b), insert(9, c), removeMin(), insert(1, d), min(), removeMin(), removeMin(). What do the value-returning calls return, and what remains?

   Answer

   The first removeMin() returns (2, b), leaving {(7,a), (9,c)}. Then (1, d) is the smallest: min() returns it without removing it, and the next two removeMin() calls return (1, d) and (7, a). Only (9, c) remains; size() is 1.

2. Insert 3, 8, 6, 10, 1, 9 into an empty max-heap of capacity 4. What is the final array, how many swaps occur, and when does the capacity grow?

   Answer

   [3] → 8 swaps with 3: [8, 3] → 6 stays: [8, 3, 6] → 10 swaps with 3, then 8: [10, 8, 6, 3] → the array is full, so the capacity grows to 8 before 1 goes in; 1 stays: [10, 8, 6, 3, 1] → 9 swaps with its parent 6 and stops under 10. Final array [10, 8, 9, 3, 1, 6], 4 swaps.

3. Call removeMax() twice on [20, 15, 18, 7, 12, 16, 4]. What is returned, and what is the final heap?

   Answer

   First, 20; 4 goes to the root: [4, 15, 18, 7, 12, 16]; larger child 18: [18, 15, 4, 7, 12, 16]; at index 2 the only child is 16: [18, 15, 16, 7, 12, 4]. Second, 18; 4 to the root: [4, 15, 16, 7, 12]; larger child 16: [16, 15, 4, 7, 12], and index 2 is a leaf. Final heap [16, 15, 4, 7, 12].

4. What is the height of a 25-item binary heap? Where does the bottom-up loop start, and how many nodes are leaves? With 0-based indices, where is the parent of index 20?

   Answer

   Height ⌊log₂ 25⌋ = 4 (16 ≤ 25 < 32). The loop starts at ⌊25/2⌋ − 1 = 11; the 13 nodes at indices 12 to 24 are leaves. Index 20's parent is ⌊19/2⌋ = 9; its first child would be 41 ≥ 25, so 20 is a leaf.

5. Turn [5, 13, 2, 25, 7, 17, 20, 8, 4] into a max-heap bottom-up. What is the array after each sink(k), and how many swaps occur?

   Answer

   n = 9, so k starts at 3. k = 3: 25 ≥ 8, 4, no change. k = 2: 2 swaps with its larger child 20: [5, 13, 20, 25, 7, 17, 2, 8, 4]. k = 1: 13 swaps with 25 and then stays, since 13 ≥ 8, 4: [5, 25, 20, 13, 7, 17, 2, 8, 4]. k = 0: 5 swaps with 25, 13, and 8 in turn: [25, 13, 20, 8, 7, 17, 2, 5, 4]. 5 swaps.

6. Heap-sort [5, 2, 8, 1, 9]. What is the array after construction and after each “root to the end + sink” round?

   Answer

   Construction: at k = 1, 2 ↔ 9; at k = 0, 5 ↔ 9, and 5 stops above its children 1 and 2: [9, 5, 8, 1, 2]. Rounds: [8, 5, 2, 1 | 9] → [5, 1, 2 | 8, 9] → [2, 1 | 5, 8, 9] → [1 | 2, 5, 8, 9]. Result [1, 2, 5, 8, 9].

7. Call changeKey(1, 2) on [15, 9, 12, 4, 8, 10, 3]. Which operation runs, and what is the final array?

   Answer

   The key drops from 9 to 2, so sink(1) runs. Index 1's children are 4 and 8; 2 < 8 (index 4), so they swap, and index 4 is a leaf. Final array [15, 8, 12, 4, 2, 10, 3]; the root and the right subtree are never examined.

8. What does kthLargest([3, 11, 6, 2, 9, 14, 5], 2) return, and which items are dropped?

   Answer

   The heap holds at most two items. After 3 and 11, the arrival of 6 drops 3: {6, 11}. 2 is dropped as soon as it enters. 9 drops 6, 14 drops 9, and 5 drops itself. The heap ends as {11, 14}, and peek() returns 11, the second largest. Dropped, in order: 3, 2, 6, 9, 5.

9. For a perfect binary tree of 1023 nodes (height 9), how many swaps does bottom-up construction make in the worst case? How many would inserting the same items one by one in increasing order make?

   Answer

   There are 2^9−h nodes of height h, each making at most h swaps: Σ h · 2^9−h = 1013, which equals n − log₂(n + 1) = 1023 − 10, less than n. Increasing insertion sends every item to the root, the 2^d nodes at depth d making d swaps each: Σ d · 2^d = 8 · 2¹⁰ + 2 = 8194, over eight times as many.

10. The adaptable queue's remove deletes the item at index 4 (3) from [10, 4, 9, 1, 3, 8, 7]. What replaces it, which repair is needed, and what is the final array?

    Answer

    It is swapped with the last item, 7, and n becomes 6: [10, 4, 9, 1, 7, 8]. 7 exceeds its parent 4, so up-heap is needed, not down-heap: 7 and 4 swap, and since 10 ≥ 7 it stops. Final array [10, 7, 9, 1, 4, 8]. The replacement came from the other branch of the tree, not the deleted node's subtree.

11.11Further reading

• M. T. Goodrich, R. Tamassia, and M. H. Goldwasser, Data Structures and Algorithms in Java (6th ed., 2014), Chapter 9: the priority queue ADT, list and heap implementations, and adaptable priority queues with location-aware entries, in Java close to these notes.
• T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms (4th ed., 2022), Chapter 6: heaps, the proof that bottom-up construction is linear, heap sort, and heap-based priority queues, formally; the ten-item example here comes from this book.
• R. Sedgewick and K. Wayne, Algorithms (4th ed., 2011), Section 2.4: the binary heap in a 1-based array with operations named swim and sink, plus indexed priority queues and multiway merging.
• R. W. Floyd, “Algorithm 245: Treesort 3” (1964): the one-page paper that introduced bottom-up heap construction, improving Williams's heapsort.

11.12References

1. T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, 4th ed., MIT Press, 2022.
2. R. W. Floyd, “Algorithm 245: Treesort 3,” Communications of the ACM, 7(12), p. 701, 1964.
3. M. T. Goodrich, R. Tamassia, M. H. Goldwasser, Data Structures and Algorithms in Java, 6th ed., Wiley, 2014.
4. Oracle, Java SE 17 API Specification: documentation for java.util.PriorityQueue.
5. R. Sedgewick, K. Wayne, Algorithms, 4th ed., Addison-Wesley, 2011.
6. J. W. J. Williams, “Algorithm 232: Heapsort,” Communications of the ACM, 7(6), pp. 347–348, 1964.

Related pages: Chapter 11 slides · Study questions · Glossary · © Sercan Külcü. All rights reserved.