Data Structures and Algorithms with C · Lecture Notes

Chapter 13: Priority Queues and Heaps

In an ordinary queue, items leave in the order in which they arrived. In many real systems, however, the item to handle first is not the one that arrived first but the one that is most urgent: the aircraft with the least fuel left, the shortest job, the nearest vertex. These notes define the operations of such a queue and implement it with a structure called a heap. A heap is a complete binary tree stored in an array. It uses no pointers, yet it behaves like a tree. The notes first set up the index rules of this array. They then write the insertion and deletion routines in C, trace them line by line, and justify their costs. A cost table and real measurements show why a heap beats simple structures such as arrays and linked lists. The last sections show how to turn an array into a heap in linear time, describe the d-ary heap and heap sort, and survey where priority queues are used.

Learning outcomes

Defining
Define a priority queue and a max/min heap; distinguish a heap from a binary search tree.
Setting up the representation
Store a complete binary tree in a 1-based array: parent i/2, children 2i and 2i+1.
Insertion and deletion
Trace the routines insert_max_heap and delete_max_heap step by step.
Analyzing
Show why insertion and deletion take O(lg n) and why the best case is Ω(1).
Comparing
Compare a heap with unsorted/sorted arrays and lists using a cost table.
Extending
Explain why bottom-up heap construction is O(n); recognize the d-ary heap.

13.1Priority queues

A queue is a structure in which items enter at one end and leave at the other. This discipline is fair: first come, first served. But it is not the right discipline for every job. In a hospital emergency room, patients are not examined in order of arrival but according to the severity of their condition. This section describes the data structure that captures such a discipline and explains why we need it.

13.1.1How it differs from a queue

An ordinary queue has two operations. Insertion puts the new item at the back of the queue; deletion takes the item at the front. This rule is called first in, first out (FIFO). In a priority queue, by contrast, every item has a priority, and deletion looks at that priority.

Definition 13.1

A priority queue is a queue in which every item carries a priority value, and the item to be removed first is determined by its priority value rather than by its arrival order. In a max priority queue the item with the highest value is handled first; in a min priority queue the item with the lowest value is handled first.

Most sources call the priority value the key. These notes use the two words interchangeably. Which value counts as “high priority” depends on the problem: in a race the shortest time is best; in an auction, the highest bid. The difference between the two kinds lies only in the direction of the comparison. For this reason the notes mostly describe the max priority queue; the min version is obtained by reversing the comparison signs.

Figure 13.1 shows the difference on four items. Each item is named by a letter and has a number as its priority: A:3, B:9, C:5, D:7. The four items arrived in this order. The ordinary queue yields the first arrival, A. The max priority queue yields B, which has the highest priority; B does not wait its turn even though it came second. On the second deletion the ordinary queue yields B and the priority queue yields D. The complete output order of the priority queue is B, D, C, A: items leave in decreasing order of priority.

Queue (FIFO): arrival orderA:3B:9C:5D:7▲ front: first in (A) leaves← insert at backMax priority queueA:3B:9C:5D:7▲ highest priority (B:9) leaves
Figure 13.1: The same four items in two structures. On the left, an ordinary queue: insertion is at the back, and the first arrival A leaves. On the right, a max priority queue: the item with the highest priority, B:9, leaves.

The definition says nothing about how the items are arranged inside the structure. It says only which item must come out first. This is an important freedom. The structure that implements the queue may arrange its items however it likes, as long as it can find and return the highest-priority item on demand. Most of these notes describe the arrangement that makes the best use of this freedom: the heap.

Common mistake

Believing that a priority queue always keeps its items sorted. The definition only determines which item comes out first. Keeping the items sorted is one way to satisfy that condition, but not the cheapest. A heap keeps only the highest-priority item ready, without sorting the rest completely; that is exactly why it is cheap.

13.1.2Why we need it

The slides motivate the priority queue with two examples. In both, arrival order does not lead to the right decision.

The photocopier. Everyone who uses a photocopier pays a fixed fee. A user who copies three pages pays the same as one who copies thirty. The owner wants to maximize earnings, that is, to serve as many users as possible in a given time. The way to do that is to give priority to the user with the shortest usage time. If the three-page job is done first, that user leaves at once and pays; even if the thirty-page job waits, total earnings rise. Here the item to handle first is the one with the smallest value: this is a min priority queue.

The airport. Consider aircraft waiting for a slot to land. Landing the aircraft that arrived first at the tower looks fair at first sight. But one cannot tell an aircraft that is almost out of fuel, “you are at the back of the queue, wait your turn.” Landing clearance goes to the aircraft with the least fuel left. This too is a min priority queue: the key is the amount of remaining fuel.

Real systems work this way too. An operating system keeps the processes that are ready to run in a priority queue. When an interrupt arrives or a process's time slice expires, the highest-priority process in the queue is given the processor. In such systems the queue changes constantly: new jobs arrive and finished jobs leave. The structure therefore has to make both insertion and removal of the highest-priority item fast. The real difficulty is keeping these two operations cheap together.

13.1.3The abstract data type

A type whose operations and behavior are specified but whose implementation is hidden is called an abstract data type (ADT). The priority queue is an ADT too. The slides give the interface of the max priority queue as follows:

/* max priority queue interface */
bool is_empty(void);
bool is_full(void);
void insert(element item);     /* O(lg n) */
bool pop_max(element *out); /* remove + return */
bool peek_max(element *top);  /* look, no removal */

The interface has five operations. is_empty and is_full query the state of the queue. In an implementation with fixed capacity, nothing can be inserted into a full queue, which is why is_full is part of the interface. insert puts an item, together with its priority, into the structure. pop_max both returns the highest-priority item and removes it from the structure; the slides call this operation delete. peek_max reads the highest-priority item without removing it.

The pop and peek operations hand back the item through a pointer parameter, not as the return value. The return value is a bool that reports whether the operation succeeded. An empty queue has nothing to remove. A function that returned the item would have to invent a “meaningless” item in that case. Returning false, in contrast, tells the caller plainly that there is no item. For a function that returns the item as a structure, there is no suitable value to signal the “empty” state either.

The interface does not say how the queue is to be implemented. A priority queue can be implemented with an unsorted array, a sorted array, a linked list, or a heap. All of them offer the same interface, and the program that uses them cannot tell the difference. The difference lies only in cost. Simple structures make one operation very cheap and the other very expensive. A heap does both in O(lg n) time. This balance makes the heap the most common implementation of the priority queue.

13.2Heap structure

A heap combines two rules. The first rule fixes the shape of the structure: a heap is a complete binary tree. The second fixes the order of the values: every node is greater than or equal to its children. This section first describes the shape rule and how it is stored in an array, then the order rule.

A note on terminology: do not confuse the data structure called a heap with the heap memory from which malloc allocates. The two have nothing in common except the name. In the C code of the slides, the array that holds the heap is called heap, and the routines have names such as insert_max_heap; the notes use the same names.

13.2.1A complete binary tree in an array

In a binary tree every node has at most two children. The node directly above a node is its parent. Nodes at the same distance from the root are on the same level. In these notes the root is on level 0.

Definition 13.2

A complete binary tree is a binary tree in which every level except possibly the last is full, and the nodes of the last level are packed from left to right without gaps.

The shape of a complete binary tree depends only on the number of nodes. A complete binary tree with 6 nodes can be drawn in only one way: the root, its two children, and three nodes at the last level, filled from the left. This rigidity pays off. If the nodes are numbered level by level, and left to right within each level, the number of every node is completely determined by the shape of the tree. The root gets number 1, its left child 2, its right child 3; the nodes of the next level continue as 4, 5, 6, 7. These numbers can be used directly as array indices.

141122731048566 0–114212374105866
Figure 13.2: The max heap 14, 12, 7, 10, 8, 6. Above, the tree view; the small numbers next to the nodes are indices. Below, the layout of the same heap in the array; cell 0 is unused.

Figure 13.2 shows a complete binary tree with six nodes and its array counterpart. Each node of the tree sits in the array cell whose index equals its number. The 14 at the root is in heap[1], the root's children 12 and 7 are in heap[2] and heap[3], and the 10, 8 and 6 on the last level are in heap[4], heap[5] and heap[6]. Cell 0 of the array is not used. This small waste simplifies the index formulas.

The most important consequence of the numbering is that the relationship between a parent and its children is found by simple arithmetic. The left child of node i is at index 2i, the right child at 2i + 1, and the parent at ⌊i/2⌋. Because integer division in C rounds down, the expression i / 2 gives this floor directly. Table 13.1 collects these rules.

Table 13.1: Index rules of a complete binary tree in a 1-based array (n is the number of items).
NodeIndex (1-based)Index (0-based)
root10
parent of ii / 2(i - 1) / 2
left child2i2i + 1
right child2i + 12i + 2
last itemnn - 1

A small count shows why the rules are correct. Level d holds 2d nodes, and the number of the first node of that level is 2d: 1, 2, 4, 8, … Let node number i be k-th from the left on its level (counting from 0); that is, i = 2d + k. Each of the k nodes to its left has two children. So its left child is at position 2k from the left one level down. Since the first number on the next level is 2d+1, the number of the left child is 2d+1 + 2k = 2(2d + k) = 2i. The right child is immediately to its right: 2i + 1. The formula for the parent is the inverse of these. Both 2i and 2i + 1 give i when divided by 2 and rounded down.

Some sources start the array at cell 0. Then every number drops by one and the formulas change: the parent is (i - 1) / 2 and the children are 2i + 1 and 2i + 2. Both layouts are correct, but a program must not mix them. The slides and these notes use the 1-based layout, which keeps the formulas simple.

Example 13.1

In a 1-based heap, the parent of node 13 is node ⌊13/2⌋ = 6. Its left child is node 2 · 13 = 26 and its right child is node 27. These children exist only if the heap has enough items: the left child exists if n ≥ 26, the right child if n ≥ 27. Node 13 is on level 3, because 8 ≤ 13 < 16; it is the 6th node from the left on its level (13 = 8 + 5, which is 5 counting from 0). If the same tree were stored in a 0-based array, this node would be at a[12]; its parent would be (12 − 1)/2 = 5 and its children 25 and 26. The same nodes are found in both layouts; only their numbers shift by one.

This representation costs nothing. In a linked tree every node carries two child pointers; for an int key that means 8 or 16 extra bytes per node. In the array these pointers are unnecessary, because a complete binary tree has no gaps between nodes and the positions of the children are computed. Since the array cells sit side by side in memory, the processor cache also works well with this structure. The gain is specific to complete binary trees. A sparse, unbalanced tree stored this way would leave most of the array empty. That is exactly why the shape rule exists in a heap.

Common mistake

Mixing up the 1-based and 0-based formulas. Suppose the array starts at cell 0 and the parent is computed as i / 2. Then the parent of cell 1, which is thought of as a child of the root, is still cell 0, but the parent of cell 2 comes out as cell 1. In the 0-based layout, however, cell 2 is the right child of the root. As a result the wrong nodes are compared and the heap silently breaks. The program does not crash; it just returns the wrong item. Such a bug is hard to find.

13.2.2A heap is not a binary search tree

The word heap should bring to mind a complete binary tree, not a binary search tree. Both structures are binary trees and in both the values obey some order, but the orders are very different. In a binary search tree the values in the left subtree of every node are smaller than the node, and those in the right subtree are larger: left < root < right. In a heap there is only the rule parent ≥ child. No order is required between the left child and the right child.

472655173449845293Binary search tree 931842553524345496477178269A max heap with the same values
Figure 13.3: The same nine values in two structures. On the left, a binary search tree: each node has smaller values on its left and larger on its right; the tree is not complete. On the right, a max heap: a complete binary tree in which every parent is larger than its children.

Figure 13.3 shows how the same nine values, 47, 26, 55, 17, 34, 49, 84, 52, 93, are placed in the two structures. In the binary search tree the root is 47; 26 is on the left and 55 on the right. The shape of the tree depends on the order in which the values arrived. In the example, 49 and 84 each have a node below them while 17 has no children at all; the tree is not complete. In the heap the root is 93, the largest value. The shape is complete: the first three levels are full and the last level has two nodes from the left. The left child of the root is 84 and the right child is 55; there is no ordering rule between these two values.

The two structures answer different questions. In a binary search tree, searching for a value is easy: at each node one goes left or right. In a heap there is no such direction; to find 34 one may have to look in both subtrees of the root. In return, the one question a heap answers is answered very fast: the largest value is always at the root. A heap is not a search structure but a priority queue structure.

13.2.3Max heaps and min heaps

Definition 13.3

A max heap is a complete binary tree in which the value of every node is not smaller than the values of its children. A min heap is a complete binary tree in which the value of every node is not larger than the values of its children. This condition on the values is called the heap property.

The phrase “not smaller than” in the definition is chosen deliberately. A parent may be equal to its child; two items with the same priority may stand in a heap as parent and child. The two parts of the definition are not sufficient separately. A tree that satisfies the heap property but is not complete is not a heap; nor is a complete tree that violates the heap property. These definitions are given to implement the max and min priority queues: a max heap implements a max priority queue, and a min heap implements a min priority queue.

1411227310485660–114212374105866916233540–192633453012520–130225maxheap examples 21724310485660–12273441058661012028335040–1102203834501112120–111221minheap examples
Figure 13.4: Three max heaps above and three min heaps below, each with its array representation underneath. Heaps with two items are valid too.

Figure 13.4 gives three examples of each kind. The first max heap above is the main example of the notes: 14, 12, 7, 10, 8, 6. Every parent is larger than its children: 14 ≥ 12, 14 ≥ 7, 12 ≥ 10, 12 ≥ 8, 7 ≥ 6. The right child of the root, 7, is smaller than 10 and 8 in the left subtree. This is not a problem; 7 and 10 have no parent–child relationship. In the min heaps below, the rule is reversed. In the first example, 2, 7, 4, 10, 8, 6, every parent is smaller than its children and the smallest value, 2, sits at the root.

The heap property links only adjacent levels. But chained together it gives a much stronger result: on any path from the root to a leaf, the values form a non-increasing sequence. From this it follows that the root holds the largest value of the whole tree.

Theorem 13.1 (The item at the root)

In a non-empty max heap, the value of every node is not larger than the value of any of its ancestors. In particular, the value at the root is the largest value in the heap.

Proof. Take a node numbered i. Going to its parent ⌊i/2⌋, then that node's parent ⌊i/4⌋, and so on, we reach the root, number 1, in finitely many steps, because each step at least halves the number. Every consecutive pair in this chain is a parent–child pair, and by the heap property the parent's value is not smaller than the child's. Chaining the inequalities gives heap[1] ≥ … ≥ heap[⌊i/2⌋] ≥ heap[i]. Since i was an arbitrary node, the root is not smaller than any value. ∎

The theorem answers the most frequent question about a priority queue, “which item is the largest?”, in O(1): it is heap[1]. The rest of the array is not sorted. In the example heap, the second largest value, 12, is at index 2, but the third largest, 10, is at index 4, not index 3. The guarantee holds only for index 1. The second largest value is always one of the root's children. The third largest may be the root's other child, or a child of the larger child.

13.2.4Heap or not?

To tell whether an array is a max heap, it is enough to look at all parent–child pairs. In the array representation the shape rule holds automatically, because indices 1..n are filled without gaps. Only the order rule remains: for every k ≥ 2 we need heap[k/2] ≥ heap[k]. No order is required between siblings or cousins. The following helper function performs this check:

bool is_heap(element a[], int n) {
  for (int k = 2; k <= n; k++)
    if (a[k / 2].x < a[k].x) return false;  /* parent < child */
  return true;
}

The loop compares each node from 2 to n once with its parent. Since every node other than the root has exactly one parent, all parent–child pairs are checked exactly once. It returns false at the first violation. The cost is at most n − 1 comparisons, that is, O(n). This function is not part of the heap, but it is very useful for testing the routines we write. All the numbers in these notes were verified with test programs that run this check after every operation.

5013024031042053560–150230340410520635(a)5013024033542051060–150230340435520610(b)91728314250–1927384152(c)
Figure 13.5: Three candidate arrays. Which one is a max heap?
Example 13.2

Figure 13.5 shows three arrays. (a) 50, 30, 40, 10, 20, 35 is a max heap. The parent–child pairs are 50 ≥ 30, 50 ≥ 40, 30 ≥ 10, 30 ≥ 20 and 40 ≥ 35; all hold. It does not matter that 35 is larger than 30; the parent of 35 is 40.

(b) 50, 30, 40, 35, 20, 10 is not a max heap. The parent of 35 at index 4 is 30 at index ⌊4/2⌋ = 2, and 30 < 35. is_heap stops at k = 4 on this array and returns false.

(c) 9, 7, 8, 1, 2 is a max heap. The tree is complete and every parent is larger than its children: 9 ≥ 7, 9 ≥ 8, 7 ≥ 1, 7 ≥ 2. It does not matter that 1 and 2 are smaller than 8, that is, that a value in the right subtree is larger than values in the left one. is_heap returned true, false, true for the three arrays, respectively.

13.2.5C definitions

The first implementation in the slides keeps the heap in a global array with an item counter. The definitions are as follows:

#define MAX_ELEMENTS 200   /* max items + 1 */
#define HEAP_FULL(n) ((n) == MAX_ELEMENTS - 1)
#define HEAP_EMPTY(n)  (!(n))

typedef struct {
  int x;          /* priority (key) */
  /* other fields */
} element;

element heap[MAX_ELEMENTS];  /* [0] unused */
int n = 0;                    /* item count */

MAX_ELEMENTS is the size of the array. Because cell 0 is unused, the heap holds at most MAX_ELEMENTS − 1 = 199 items; hence the “max items + 1” in the comment. The indices in use are 1..199. The macro HEAP_FULL(n) tests whether the item count has reached this limit, and HEAP_EMPTY(n) tests whether the item count is zero. The expression !(n) yields 1 if n is zero and 0 otherwise.

The item type element is a structure. Its only field, x, holds the priority. In a real application the structure would hold other fields too: a process number, an aircraft's flight code. The heap routines look only at x; the other fields travel with the item. For this reason the routines copy items as whole structures, not as integers. The assignment heap[i] = heap[j] copies all fields of the structure at once. In the examples of these notes the structure holds a single int, so it is 4 bytes.

Parenthesizing the parameter in a macro is not a habit but a necessity. A macro is not a function; the preprocessor substitutes the text as it is. Suppose #define HEAP_EMPTY(n) (!n) had been written. The call HEAP_EMPTY(a + b) expands to (!a + b). Since the ! operator is applied before +, this expression is evaluated as (!a) + b; for a = 0, b = 5 the result is 6, which means “empty”. With the correct definition the expression becomes (!(a + b)) and yields 0. The outer parentheses serve the same purpose: when the result of the macro is used inside a larger expression, it must stay together as a whole.

Common mistake

Defining the array as element heap[MAX_ELEMENTS - 1], that is, with 199 items (indices 0..198). HEAP_FULL considers the heap full only when n = 199. At the 199th insertion, n rises to 199 and the item is written to heap[199], a cell outside the array. This bug was tried with a test program: the 199th insertion wrote to the memory just after the array and the program went on without any warning. The undefined-behavior sanitizer (-fsanitize=undefined) stopped only when the same cell was read, with the message “index 199 out of bounds for type 'element[199]'”. The size of the array must be MAX_ELEMENTS.

A global array and a global counter are a simple start, but they have limits. The program can have only one heap. The capacity is fixed at compile time. The routines do not take the array they work on as a parameter. These drawbacks can be removed by using a structure. But the logic of the routines is easiest to see on the global array; insertion and deletion are therefore written in that form first.

13.3Insertion

When a new item is inserted into a heap, two rules must be preserved at once: the tree must stay complete, and no parent may be smaller than its children. Insertion handles the two rules in turn: it fixes the shape first, then the order.

13.3.1Make room first, then sift

When a node is added to a complete binary tree, where the new node goes is already determined: the first empty position on the last level. If the last level is full, a new level is opened and its leftmost position is used. In the array representation the index of this position is n + 1. So the position to open for the new item is known exactly. This position is opened first; the tree is complete again.

But the new item may be larger than its parent. Then the heap property is broken at this parent–child pair. To repair it, the new item is moved upward to its proper position. If the parent is smaller than the new item, the parent moves down one level and the candidate position for the new item moves up one level. This continues until a parent not smaller than the new item, or the root, is reached. This upward movement is called sifting up (up-heap).

Figure 13.6 shows the insertion of 15 into the heap 14, 12, 7, 10, 8, 6 in five moments. Initially the heap has six items. The first empty position is 7; it is the right child of node 3, the node holding 7. The new item, 15, is larger than 7, so 7 is shifted down one level to position 7 and the hole moves up to position 3. The parent of position 3 is the 14 at the root. 15 is larger than that too; 14 goes down to position 3 and the hole moves up to position 1, the root. The root has no parent. 15 is written at the root and the heap property is restored. The final state is 15, 12, 14, 10, 8, 6, 7.

1411227310485660–1142123741058667891011initialn = 6 1411227310485667empty0–1142123741058667891011+15n = 7item15 1411223104856677empty0–11421237410586677891011+15n = 7item15 1122143104856677empty0–114212314410586677891011+15n = 7item15 1511221431048566770–115212314410586677891011+15n = 7
Figure 13.6: Inserting 15. From top to bottom: the initial state; opening the first empty position (7); shifting 7 down; shifting 14 down; writing 15 at the root. The orange circle shows the hole, and the box on the right shows the item waiting to be placed.

Note that the movement takes place along a single path. The path from the new position to the root is 7 → 3 → 1. The rest of the heap, for example the subtree of 12, is not touched at all. This is the source of the cheapness of insertion. The length of the path equals the height of the tree, and the height of a complete binary tree grows with the logarithm of the number of items.

Why does sifting up preserve the heap property? Every parent that moves down along the path is smaller than the new item. The children of the position it moves to were already its grandchildren in its old position; by the heap property they are not larger than it. So the parent that moves down obeys the rule in its new place as well. The new item, where it stops, is not larger than its parent. Nor is it smaller than its children: one of them is the parent that it displaced downward, and the other is the old child of that parent. Both are smaller than the new item. Thus at the end of the insertion all parent–child pairs obey the rule again.

13.3.2insert_max_heap: shifting, not swapping

The insertion routine in the slides is as follows:

void insert_max_heap(element item) {
    if (HEAP_FULL(n)) {
    heap_full();             /* error message */
    return;
  }
  int i = ++n;
  while (i != 1) {            /* i == 1: at the root */
    if (item.x <= heap[i / 2].x) break;
    heap[i] = heap[i / 2];  /* move parent down */
    i /= 2;                   /* go up a level */
  }
  heap[i] = item;
}

The routine first checks whether the heap is full. If it is, heap_full() is called and the routine returns without inserting. heap_full is a simple routine that prints an error message; the slides do not show its body. The test programs used a one-line function that writes “heap full” to the standard error stream.

The line int i = ++n; does two things. ++n first increments the item count and then yields the incremented value; i therefore receives the index of the first empty position, that is, the new last position. After this line heap[i] holds no meaningful value yet. The new item is not written there immediately, because that may not be its place. i marks the current position of the hole.

The loop condition is i != 1. When i is 1, the hole has reached the root, and the root has no parent; we cannot go higher. The first statement of the loop compares the new item with the parent of the hole. If item.x <= heap[i / 2].x, the parent is large enough, the hole is the place for the new item, and the loop ends with break. Otherwise the parent is copied into the hole, that is, one level down: heap[i] = heap[i / 2]. Then i /= 2 moves the hole up to the parent's old position. When the loop ends, i marks the place of the new item and heap[i] = item writes the item there.

The idea behind the routine deserves attention: there is no swap. Many sources describe sifting up by writing the new item at the end and then exchanging it with its parent repeatedly. Each exchange needs a temporary variable and three assignments. The hole method used here does not carry the new item along the path. Only the larger ancestors are shifted down one level each, and each shift is a single assignment. The new item is written once, at the very end. For an insertion that climbs k levels, swapping makes 3k assignments, whereas this method makes k + 1. When the item type is a large structure, the difference matters even more.

Common mistake

Writing the loop condition as i > 0 or i >= 1. If the loop is entered with i equal to 1, it reads heap[i / 2], that is, the unused heap[0]. Cell 0 holds a meaningless value. If that value is smaller than the new item, the assignment heap[1] = heap[0] copies the meaningless value into the root, i becomes 0, and the new item is written to heap[0], outside the heap. The root is left with a meaningless value and the new item is lost. To stop at the root, the condition must be i != 1 (or i > 1).

13.3.3Code trace: insert(15)

Table 13.2 traces the insertion of Figure 13.6 through the lines of the code. The line numbers follow the trace slide in the slides: line 2 is the full check, line 6 is int i = ++n;, line 7 the loop condition, line 8 the comparison, line 9 the shift, line 10 i /= 2, and line 12 the final write. Initially the heap is 14, 12, 7, 10, 8, 6 and n = 6.

Table 13.2: Trace of insert_max_heap(15). The array column shows heap[1..7]; _ marks the hole.
Lineniheap[i/2]Condition / actionheap[1..7]
26——HEAP_FULL(6) is false: there is room14, 12, 7, 10, 8, 6, —
6777i = ++n: first empty position14, 12, 7, 10, 8, 6, _
77777 ≠ 1: enter the loop14, 12, 7, 10, 8, 6, _
877715 ≤ 7? No14, 12, 7, 10, 8, 6, _
9777heap[7] = heap[3]14, 12, _, 10, 8, 6, 7
107314i /= 214, 12, _, 10, 8, 6, 7
7, 873143 ≠ 1; 15 ≤ 14? No14, 12, _, 10, 8, 6, 7
97314heap[3] = heap[1]_, 12, 14, 10, 8, 6, 7
1071—i /= 2_, 12, 14, 10, 8, 6, 7
771—i = 1: the root is reached, the loop ends_, 12, 14, 10, 8, 6, 7
1271—heap[1] = item15, 12, 14, 10, 8, 6, 7

The “hole” in the table is a notational convenience. In memory that cell is not empty; it holds a copy of the old value. After the line heap[7] = heap[3], the value 7 is in both cell 3 and cell 7. The copy in cell 3 is now meaningless, because it will be overwritten in the next step. The trace therefore shows that cell as a hole. The same happens with 14: after heap[3] = heap[1] the 14 is in two cells, and the copy at the root is overwritten by 15 on the last line.

The loop runs fully twice and ends at the third check because i == 1. In total there are two comparisons, two shifts and one final write. The new item has climbed two levels along the path. That it stops at the root is no coincidence: 15 is larger than every value in the heap, and by Theorem 13.1 the largest value must end up at the root.

13.3.4Code trace: insert(109)

In the second insertion the heap is 15, 12, 14, 10, 8, 6, 7 with n = 7, and 109 is inserted. 109 is larger than all items, so this insertion is a worst case: the item will climb all the way to the root. The last level (4, 5, 6, 7) is full. The new position, 8, is therefore the first position of a new level, and it is the left child of node 4, that is, of 10.

Table 13.3: Summary of the trace of insert_max_heap(109). Each row is one iteration of the loop.
Roundii/2ComparisonActionheap[1..8] (end of round)
start84—i = ++n = 815, 12, 14, 10, 8, 6, 7, _
184109 ≤ 10? Noheap[8] = heap[4], i = 415, 12, 14, _, 8, 6, 7, 10
242109 ≤ 12? Noheap[4] = heap[2], i = 215, _, 14, 12, 8, 6, 7, 10
321109 ≤ 15? Noheap[2] = heap[1], i = 1_, 15, 14, 12, 8, 6, 7, 10
end1—i = 1: the loop endsheap[1] = item109, 15, 14, 12, 8, 6, 7, 10
1511221434856677108ii/20–11521231441058667781091011▲ i▲ i/2insert(109)n = 8item109 1512143124856677108ii/20–11521231441258667781091011▲ i▲ i/2insert(109)n = 8item109 1152143124856677108ii/20–11521531441258667781091011▲ i▲ i/2insert(109)n = 8item109 1091152143124856677108i0–110921531441258667781091011▲ iinsert(109)n = 8
Figure 13.7: Four moments during insert(109). From top to bottom: shifting 10, 12 and 15 down one level each; writing 109 at the root. i marks the hole and i/2 marks the parent being compared.

The loop runs fully three times: the path from the new position to the root is 8 → 4 → 2 → 1, which has three edges. Each round makes one comparison and one shift. At the fourth check i == 1 and the loop ends without a comparison. The three items on the path, 10, 12 and 15, have each moved down one level. The items off the path, 14, 8, 6 and 7, have not moved. This insertion did the most work possible in a heap of 8 items. A complete binary tree with 8 items has four levels, and the new item climbed from the bottom level to the root.

13.3.5Repeated insertion

The insertion example in the slides consists of five values: 15, 109, 107, 3 and 15 are inserted in turn into the heap 14, 12, 7, 10, 8, 6. The first two were traced above. The remaining three insertions behave differently; Table 13.4 gives the path and result of each insertion.

Table 13.4: Five consecutive insertions. “Path” lists the indices the hole passes through, from the new position to the position where it stops.
InsertionNew positionPathShiftsHeap (after)
+1577 → 3 → 1215, 12, 14, 10, 8, 6, 7
+10988 → 4 → 2 → 13109, 15, 14, 12, 8, 6, 7, 10
+10799 → 4 → 22109, 107, 14, 15, 8, 6, 7, 10, 12
+310100109, 107, 14, 15, 8, 6, 7, 10, 12, 3
+151111 → 51109, 107, 14, 15, 15, 6, 7, 10, 12, 3, 8

In the insertion of 107, the first empty position is 9; its parent is the 12 at position 4. Since 107 > 12, 12 shifts down to position 9 and the hole moves up to 4. The parent of 4 is the 15 at position 2; since 107 > 15, 15 shifts down too and the hole moves up to 2. The parent of 2 is the 109 at the root, and 107 ≤ 109. The parent is large enough, the loop stops, and 107 is written at position 2. This insertion stopped in the middle of the path without reaching the root.

In the insertion of 3, the new position is 10 and its parent is the 8 at position 5. Since 3 ≤ 8, the loop ends with break at the very first comparison. No shift is made and 3 is written directly at position 10. This is the best case of insertion: one comparison and one write, that is, constant work however large the heap is.

Finally the second 15 is inserted. The new position is 11; its parent is again the 8 at position 5. Since 15 > 8, 8 shifts down to position 11 and the hole moves up to 5. The parent of 5 is the 107 at position 2, and 15 ≤ 107. 15 is written at position 5. The heap now has two 15s: one at position 4 and one at position 5. These two items are siblings and there is no order rule between them. The phrase “not smaller than” in the definition allows items of equal priority.

109110721431548566771081290–110921073144155866778109121011+107n = 9 109110721431548566771081293100–1109210731441558667781091210311+3n = 10 1091107214315415566771081293108110–110921073144155156677810912103118+15n = 11
Figure 13.8: Three states after inserting 107, 3 and 15. The orange node is the position where the most recently inserted item came to rest.

Figure 13.8 shows the results of these three insertions. The numbers of shifts in the five insertions are 2, 3, 2, 0 and 1. The insertion of 3 made no shift at all; this is the best case and takes constant time. 109 climbed all the way to the root; this is the worst case and takes time proportional to the height. The cost of the same routine varies between these two extremes depending on the size of the inserted value.

13.3.6The cost of insertion

The cost of insertion is determined by the number of iterations of the loop. Each iteration does constant work: one comparison, one shift and one division. The number of iterations is the number of levels the hole climbs. The hole can climb from the bottom all the way to the root; so the number of iterations is at most the height of the tree. What remains is to find the height of a complete binary tree.

level 01 nodelevel 12 nodeslevel 24 nodeslevel 38 nodeslevel 416 nodesheight ⌈lg(n+1)⌉
Figure 13.9: The levels of a complete binary tree. Each level has twice as many nodes as the previous one: 1, 2, 4, 8, 16. The arrow shows the longest path along the height.
Theorem 13.2 (Height of a complete binary tree)

A complete binary tree with n ≥ 1 nodes has ⌊lg n⌋ + 1 = ⌈lg(n + 1)⌉ levels. A path from a leaf to the root has at most ⌊lg n⌋ edges.

Proof. Number the levels of the tree from 0 to h. Levels 0 through h − 1 are full and hold 1 + 2 + … + 2h−1 = 2h − 1 nodes. The last level has at least 1 and at most 2h nodes. Hence 2h ≤ n ≤ 2h+1 − 1 < 2h+1. Taking logarithms gives h ≤ lg n < h + 1, that is, h = ⌊lg n⌋. The number of levels is h + 1. For the second equality, the inequality 2h < n + 1 ≤ 2h+1 gives ⌈lg(n + 1)⌉ = h + 1. A path from the root to a node on the bottom level has h edges. ∎

In the array representation this result has a simple counterpart. The level of the node with index i is ⌊lg i⌋, and every i /= 2 decreases the level by one. To get from index n down to 1 takes exactly ⌊lg n⌋ halvings. For example, for n = 8, 8 → 4 → 2 → 1 is three halvings, and ⌊lg 8⌋ = 3. The insertion of 109 made exactly that many shifts.

Table 13.5: The cost of insertion.
CaseExampleShiftsCost
Bestinserting 30Ω(1)
Worstinserting 109as many as the height: ⌊lg n⌋O(lg n)
General—0 … ⌊lg n⌋O(lg n)

Table 13.5 collects the result. The time complexity of insertion is O(lg n); its best case is Ω(1). Here O denotes an upper bound and Ω a lower bound. When the best and worst cases of an operation are of the same order, the cost is written with Θ, a tight bound. In insertion the two extremes differ, so a single Θ cannot be written; the worst case, however, is Θ(lg n). The extra memory is O(1): only the variable i and the parameter item are used.

These numbers mean a great deal at scale. In a heap of one million items, ⌊lg 106⌋ = 19; even the worst insertion makes 19 shifts. For a billion items the number is 29. When the number of items grows a thousandfold, the work grows by only 10 shifts.

For values that arrive in random order, insertion often comes nowhere near the worst case. An experiment inserted one million random values one by one into an empty heap and counted 1,279,942 shifts in total, an average of 1.3 shifts per insertion. When the same numbers were inserted in increasing order, so that each new value is larger than all earlier ones, the total was 17,951,445 shifts. This is the worst case, in which every insertion climbs to the root, and the total equals ⌊lg 1⌋ + ⌊lg 2⌋ + … + ⌊lg n⌋. The reason a random value most likely stays at the leaf level is simple: in a complete binary tree about half of the nodes are leaves and a quarter are one level above the leaves.

13.4Deletion

Removing an item from a max heap is the main job of a priority queue. The item to remove is known: the largest item at the root. Reading it is easy. The hard part is turning the remaining structure back into a heap after the item is removed. As with insertion, deletion first repairs the shape and then the order; this time, though, the repair works from the top down.

13.4.1Remove the root, place the last item

When the root is removed, a hole appears at the top of the tree. If the tree is to stay complete, the position that must be vacated when the item count drops by one is not the root but the last position, n. So the item in the last position is taken out of its place and a home is sought for it. The search starts from the hole at the root.

The last item is most likely a small value, because it is a leaf. If it is not larger than both children of the root, it cannot be put there. At each step three values are examined: the two children of the hole and the item to be placed. The largest of the three goes into the hole. If the largest is the item to be placed, its home has been found. Otherwise the larger child moves up one level into the hole, and the hole moves down to that child's old position. This downward movement is called sifting down (down-heap). The home is also found when the hole has no children left: the hole is a leaf.

3011522831141453667108990–130215328411514637681099initialn = 9 115228311414536671080–13021532841151463768109delete → 30n = 8 · out = 30temp9 281152311414536671080–12821532841151463768109delete → 30n = 8 · out = 30temp9 2811529311414536671080–1282153941151463768109delete → 30n = 8 · out = 30
Figure 13.10: Removing the root. From top to bottom: the start; removing 30 and taking out the last item, 9; moving the larger child, 28, up; 9 settling at position 3.

Figure 13.10 shows this on the heap 30, 15, 28, 11, 14, 3, 6, 10, 9. The first item to remove is the 30 at the root. The last item, 9, is taken out of position 9; the item count drops to 8. The children of the root are 15 and 28; the larger is 28. Since 28 > 9, 28 moves up to the root and the hole moves down to position 3. The children of position 3 are the 3 at position 6 and the 6 at position 7; the larger is 6. Since 9 ≥ 6, 9 settles in the hole at position 3. The new heap is 28, 15, 9, 11, 14, 3, 6, 10.

Choosing the larger child is not arbitrary. The item that moves into the hole becomes the parent of the other child. If the smaller child moved up, the larger child would become its child and the heap property would be broken at once. When the larger child moves up, it is not smaller than its smaller sibling or than its own old children; the heap property is preserved.

13.4.2delete_max_heap

The slides give a corrected version of the deletion routine from the textbook:

bool delete_max_heap(element *out) {
  if (HEAP_EMPTY(n)) return false;
  *out = heap[1];          /* root is returned */
  element temp = heap[n--];  /* find its slot */
  int i = 1, j = 2;
  while (j <= n) {
    if (j < n && heap[j].x < heap[j + 1].x) j++;
    if (temp.x >= heap[j].x) break;
    heap[i] = heap[j];      /* move child up */
    i = j; j *= 2;
  }
  heap[i] = temp;
  return true;
}

The routine first checks whether the heap is empty. If so, it returns false and touches nothing. Otherwise the item at the root is copied to *out. out is a pointer to the caller's variable; the assignment *out = heap[1] writes into the caller's variable. By definition, the first item to be removed is the first item of the array.

The line element temp = heap[n--]; copies the item in the last position into temp and decrements the item count. n-- is the postfix operator: the expression first yields the old value of n, and then n decreases. So heap[9] is read and n becomes 8. From this moment on, heap[9] no longer belongs to the heap. The last item has been taken out so that the complete tree stays intact, and a home will now be sought for it starting from the root.

i marks the candidate position of temp, that is, the hole; at first it is the root. j marks the children of i; at first it is 2, the left child. The loop runs as long as j <= n, that is, as long as i has at least one child. The first statement of the loop chooses the larger child: if there is a right child and it is larger than the left one, j is incremented. The second statement compares temp with the larger child. If temp is not smaller than it, the home has been found and the loop ends with break. Otherwise the larger child moves into the hole: heap[i] = heap[j]. The last statement moves the hole down to the moved child's old position, i = j, and takes j to its left child, j *= 2. When the loop exits, temp is written into the hole and true is returned.

The job of the test j < n is important. j marks the left child; the right child is at j + 1. If j == n, the left child is the last item of the heap and there is no right child. In that case heap[j + 1] does not belong to the heap. The condition j < n guarantees that the right child exists before heap[j+1] is read. Because the && operator is evaluated with short-circuiting, the second comparison is not made at all if the condition is false.

The slides call this version “corrected”. The textbook version returns the item as the return value and writes return 0; for an empty heap. If the return type is a structure such as element, this line does not compile, because an integer cannot be converted to a structure. This line was tried in a test file, and the compiler stopped with the error “returning 'int' from a function with incompatible result type 'element'”. The suggested fix, as in the interface, is to make the return value a bool that reports success or failure and to return the removed item through a pointer parameter. Then there is no need to invent a meaningless item for an empty heap.

The routine is called like this:

element e;
if (delete_max_heap(&e))
  printf("removed: %d\n", e.x);
else
  printf("heap is empty\n");

&e is the address of the variable e. The assignment *out = heap[1] inside the routine writes to this address, that is, to e. In C, function parameters are passed by value. For a function to modify the caller's variable, it must receive the address of that variable. The pointer parameter provides this here.

13.4.3Code trace: the first deletion

Table 13.6 traces the first call of delete_max_heap on the heap 30, 15, 28, 11, 14, 3, 6, 10, 9 line by line. The line numbers follow the trace slide in the slides: line 2 is the empty check, line 3 the copy of the root, line 4 the removal of the last item, line 6 the loop condition, line 7 the choice of the larger child, line 8 the comparison, line 9 the move, line 10 the advance, and line 12 the final write.

Table 13.6: Trace of the first delete_max_heap. The array column shows heap[1..9], and _ marks the hole; the cell beyond n is in parentheses.
LinenijCondition / actionheap[1..9]
29——HEAP_EMPTY(9) is false30, 15, 28, 11, 14, 3, 6, 10, 9
39——*out = 30_, 15, 28, 11, 14, 3, 6, 10, 9
48——temp = 9, n = 8_, 15, 28, 11, 14, 3, 6, 10, (9)
5812hole at the root, j at the left child_, 15, 28, 11, 14, 3, 6, 10, (9)
68122 ≤ 8: enter the loop_, 15, 28, 11, 14, 3, 6, 10, (9)
781315 < 28: j++_, 15, 28, 11, 14, 3, 6, 10, (9)
88139 ≥ 28? No_, 15, 28, 11, 14, 3, 6, 10, (9)
9813heap[1] = heap[3]28, 15, _, 11, 14, 3, 6, 10, (9)
10836i = j; j *= 228, 15, _, 11, 14, 3, 6, 10, (9)
6, 78376 ≤ 8; 3 < 6: j++28, 15, _, 11, 14, 3, 6, 10, (9)
88379 ≥ 6? Yes: break28, 15, _, 11, 14, 3, 6, 10, (9)
12837heap[3] = temp28, 15, 9, 11, 14, 3, 6, 10, (9)
13837return true; the caller receives 3028, 15, 9, 11, 14, 3, 6, 10

The loop was entered twice, made one move, and ended with break in the second round. 9 settled at position 3 without sinking to the bottom. This is an example of “landing in the middle”: the last item found its place halfway along the path from the root to a leaf. A total of four comparisons were made: in each round one to compare the children and one to compare temp with the larger child. Two comparisons per round are why sifting down is slightly more expensive than the insertion loop.

The parenthesized 9 in the last column of the table shows a subtlety. After n-- the cell 9 is not erased; it still holds a copy of 9. But since n = 8, none of the routines looks at that cell as part of the heap. At the next insertion, a new item will be written into that cell. In a C array, “deleting” does not empty a cell; it moves the boundary.

13.4.4Code trace: the second deletion

At the second call the heap is 28, 15, 9, 11, 14, 3, 6, 10 with n = 8. This time the last item, 10, will sink all the way to a leaf. Table 13.7 summarizes the rounds of the loop.

Table 13.7: Trace of the second delete_max_heap (*out = 28, temp = 10, n = 7).
RoundiChildrenLarger child (j)Comparisonheap[1..7] (end of round)
1115, 915 (2)10 ≥ 15? No: move15, _, 9, 11, 14, 3, 6
2211, 1414 (5)10 ≥ 14? No: move15, 14, 9, 11, _, 3, 6
35none (j = 10 > 7)—the loop is not entered15, 14, 9, 11, _, 3, 6
end5——heap[5] = temp15, 14, 9, 11, 10, 3, 6
2811529311414536671080–128215394115146376810delete_max_heap()n = 8 1512931141453667ij0–1152153941151463768▲ i▲ jdelete_max_heap()n = 7 · out = 28temp10 1512931141453667ij0–1152153941151463768▲ i▲ jdelete_max_heap()n = 7 · out = 28temp10 1511429311410536670–1152143941151063768delete_max_heap()n = 7 · out = 28
Figure 13.11: Four moments during the second deletion. From top to bottom: the start; moving 15 to the root; moving 14 to position 2; writing 10 at position 5, a leaf.

In the first round the children of the root are 15 and 9. Since the left child is not smaller than the right one, j stays at 2. Since 10 < 15, 15 moves up to the root and the hole moves down to 2. In the second round the children of 2 are 11 and 14; the right one is larger and j becomes 5. Since 10 < 14, 14 moves up and the hole moves down to 5. The left child of 5 would be at position 10, but 10 > n = 7, so position 5 is a leaf. The loop condition becomes false and 10 is written into the hole. The caller receives 28; the new heap is 15, 14, 9, 11, 10, 3, 6.

This call is the worst case of deletion: the last item sank from the root all the way to a leaf. In a heap with 8 items, the leaf level is level 2 or 3. 10 came to rest in a leaf on level 2 of the 7-item heap, having sunk two levels. The two deletions together show the two behaviors of deletion: the last item may land in the middle of the path or sink all the way to the bottom.

13.4.5Deleting until the heap is empty

What happens if we keep removing items from the heap until it is empty? Table 13.8 shows the remaining seven removals. In each row, the removed item is the largest item, which is at the root at that moment; the last item settles into its new place by sifting down.

Table 13.8: Successive removals from the heap 15, 14, 9, 11, 10, 3, 6. The outputs began with 30 and 28.
RemovedLast itemPosition where it settledHeap (after)
156414, 11, 9, 6, 10, 3
143511, 10, 9, 6, 3
113410, 6, 9, 3
10339, 6, 3
9326, 3
6313
33— (it was the last item)empty

The output order is 30, 28, 15, 14, 11, 10, 9, 6, 3: the items came out in decreasing order. This is no coincidence. Each removal yields the largest of the remaining items, and removing the largest items one after another produces a decreasing sequence. One detail of the table also stands out. The value 3 was the “last item” five times in a row, and each time it was placed again by a journey from the root. When 6 is removed in the sixth removal, only 3 remains in the heap. In the seventh removal 3 is both the root and the last item; temp = heap[n--] takes it, n becomes 0, the loop is not entered, and 3 is written into the unused cell 1. The heap is empty, and an eighth call returns false.

This observation is the idea of an important algorithm. If n items are put into a heap and the root is then removed n times, the items come out sorted. This is the idea of heap sort. Since each removal takes O(lg n) time, the sort takes O(n lg n) time. A version of heap sort that uses no extra array also appears in these notes.

13.4.6The cost of deletion

The cost of deletion too is determined by the number of iterations of the loop. Each iteration moves the hole down one level and makes at most two comparisons and one move. The hole starts at the root and must stop at the bottom level at the latest. By Theorem 13.2, at most ⌊lg n⌋ iterations are made. The worst case of deletion is therefore O(lg n); the number of comparisons is at most 2⌊lg n⌋.

The best case of deletion is also Ω(1). If the last item is not smaller than both children of the root, it settles in the first round. This happens, for example, when two items remain in the heap: when the root is removed, n drops to 1, the loop is never entered because j = 2 > n, and the last item is written directly at the root. In a heap with many items of equal priority, the last item often settles immediately too. But in a large heap with distinct values, the last item comes from a leaf and is usually small, so it sinks down to near the leaves. For this reason, unlike insertion, deletion runs close to the worst case on average even for random data. In a heap built from one million random values, the first thousand deletions made 18.93 rounds on average; ⌊lg 106⌋ = 19. The extra memory is again O(1): temp, i and j.

Common mistake

In deletion, moving the larger child of the root up to the root and carrying the hole downward, but not filling the hole with the last item in the end. This method leaves the hole at an arbitrary position on the leaf level. If the hole is not in the last position, a gap appears in the array and the tree stops being complete. In deletion the shape is preserved first: the position removed is always n, and the item whose home is sought is the one that comes from there.

13.4.7Two faulty versions

The deletion routine looks small, but details in two of its lines determine its correctness. Why these details are needed can be seen from two versions that break them.

The first child instead of the larger child. If the line if (j < n && heap[j].x < heap[j + 1].x) j++; is removed from the loop, the left child is chosen in every round. With this version, 30 was removed from the heap 30, 15, 28, 11, 14, 3, 6. The last item is 6. The left child, 15, moves up to the root because 6 < 15; the hole moves down to 2, where the left child 11 moves up, and 6 is written at position 4. The result is 15, 11, 28, 6, 14, 3. The 15 at the root is smaller than its right child 28; the heap property is broken. The next removal returns 15, not 28, as the largest item. The program does not crash; it just returns the wrong item.

Without the j < n test. If this test is skipped, heap[n + 1] is read when j == n. This cell is outside the heap. In delete_max_heap there is an interesting situation: after n--, heap[n + 1] holds the copy of temp itself, the item whose home is being sought. If that copy is selected, the comparison becomes temp.x >= temp.x and the loop stops at the right place. For this reason, in this routine the bug does not change the result; even in half a million random trials of mixed insertions and removals no wrong result was seen. But that is an accident and does not show that the code is correct. When the same loop is used in bottom-up heap construction, a[n + 1] may lie outside the array. In an array of 6 items, when this test was removed, the value 99 just after the array entered the heap and a 3 in the array was lost. The j < n test must therefore be written in every sift-down loop.

13.5Improving the implementation

The insertion and deletion routines work correctly, but they depend on a global array. This section improves the routines in three directions: moving the heap into a structure, writing the min heap, and handling items whose priority changes over time.

13.5.1A structure instead of a global array

With a global array, a program can have only one heap. An operating system, however, keeps many queues: a separate ready queue for each processor, and another queue for timers. The capacity is also fixed at compile time. To remove these drawbacks, the slides gather the array and the item count in one structure and allocate the array at run time:

typedef struct { element *a; int n, capacity; } Heap;

Heap *heap_create(int capacity) {
  Heap *h = malloc(sizeof *h);
  if (h == NULL) return NULL;
  h->a = malloc((capacity + 1) * sizeof *h->a);
  if (h->a == NULL) { free(h); return NULL; }
  h->n = 0; h->capacity = capacity;
  return h;
}
void heap_destroy(Heap *h) { if (h) { free(h->a); free(h); } }

The Heap structure has three fields. a is the address of the array allocated on the heap memory. n holds the item count, and capacity holds the maximum number of items it can take. Since every heap is a separate Heap, a program can have as many heaps as it wants. The routines take the heap they work on as a parameter.

heap_create allocates two separate blocks. The first is the structure itself: malloc(sizeof *h). Here sizeof *h is the size of the type that h points to, that is, Heap. Not repeating the type name keeps the line correct if the type changes later. The second block is the array. Because cell 0 is unused, capacity + 1 cells are allocated. The result of both allocations is checked. If the second allocation fails, it is not enough to return NULL; the structure allocated earlier must also be given back with free(h). Otherwise that block would remain as a piece of memory nobody can point to; that is, it would leak.

heap_destroy releases the blocks in the reverse order of allocation. The array is released first and the structure second, because the address of the array is inside the structure; if the structure were released first, h->a could not be read. The if (h) check makes a call with a NULL pointer harmless. This is consistent with the fact that free(NULL) does nothing.

The slides do not give the insertion and removal routines of the structure version; the suggestion is to report success with true/false and to pass the item through a pointer. The following two routines apply this suggestion. Their bodies are the same as the global versions; only h->a is written instead of heap and h->n instead of n:

bool heap_insert(Heap *h, element item) {
  if (h->n == h->capacity) return false;   /* full */
  int i = ++h->n;
  while (i != 1 && item.x > h->a[i / 2].x) {
    h->a[i] = h->a[i / 2];
    i /= 2;
  }
  h->a[i] = item;
  return true;
}

bool heap_pop(Heap *h, element *out) {
  if (h->n == 0) return false;             /* empty */
  *out = h->a[1];
  element temp = h->a[h->n--];
  int i = 1, j = 2;
  while (j <= h->n) {
    if (j < h->n && h->a[j].x < h->a[j + 1].x) j++;
    if (temp.x >= h->a[j].x) break;
    h->a[i] = h->a[j];
    i = j; j *= 2;
  }
  h->a[i] = temp;
  return true;
}

In the insertion routine, a full heap is no longer reported with an error message but with a return value of false; the caller decides what to do. The loop condition has also become a little shorter: the conditions i != 1 and “the parent is smaller” are combined in a single while. Because && is evaluated with short-circuiting, h->a[0] is never read when i == 1. The two forms do the same job.

Figure 13.12 draws this structure as it appears in memory. Only the pointer h lives on the program stack. The structure and the array are in heap memory; the a field of the structure holds the starting address of the array.

program stack heap memory h a n = 3 capacity = 4 0 1 2 3 4 – 30 5 20
Figure 13.12: Memory view of a heap created with heap_create(4) into which 20, 5 and 30 have been inserted. The array has capacity + 1 = 5 cells; cell 0 is unused and cell 4 is still empty.

This version was tested with a counting malloc/free wrapper. The wrapper consists of two small functions that increment a counter on every successful allocation and every release; they are substituted for malloc and free with macros. The test began with heap_create(4) and tried to insert the values 20, 5, 30, 10, 40. The first four insertions returned true and the fifth returned false, because the capacity is 4. Then items were removed until the heap was empty, and 30, 20, 10, 5 came out. After heap_destroy, the counters showed 2 allocations and 2 releases; there is no leak. The call heap_destroy(NULL) also passed without trouble. With this compiler configuration, sizeof(Heap) is 16 bytes: an 8-byte pointer and two 4-byte ints.

The capacity of the array can also be made unbounded by doubling it with realloc when it fills up. Then insertion never returns false; the single insertion that triggers the growth takes Θ(n), but the amortized cost does not change. The total copying cost of doubling does not exceed 2n over n insertions.

13.5.2Min heap

The photocopier and airport examples would call for a min priority queue. The routines of a min heap differ from those of a max heap in only two respects: the name of the routine and the direction of the comparisons. The slides give the insertion routine:

void insert_min_heap(element item) {
  /* ... same full check ... */
  int i = ++n;
  while (i != 1) {
    if (item.x >= heap[i / 2].x) break; /* >= ! */
    heap[i] = heap[i / 2];
    i /= 2;
  }
  heap[i] = item;
}

The only change is in the break condition: item.x >= … instead of item.x <= …. As long as the new item is smaller than its parent, the parent moves down; if the new item is not smaller than its parent, its place has been found. The comment on the second line of the code says that the full check is the same as in the max version; it is omitted for brevity. In the test program it was compiled with this check added.

In the removal routine, two places change: the smaller child is chosen instead of the larger one, and the stopping condition is reversed.

bool delete_min_heap(element *out) {
  if (HEAP_EMPTY(n)) return false;
  *out = heap[1];
  element temp = heap[n--];
  int i = 1, j = 2;
  while (j <= n) {
    if (j < n && heap[j].x > heap[j + 1].x) j++;  /* smaller child */
    if (temp.x <= heap[j].x) break;               /* <= ! */
    heap[i] = heap[j];
    i = j; j *= 2;
  }
  heap[i] = temp;
  return true;
}
Table 13.9: Differences between the max heap and min heap routines.
PlaceMaxMin
insert: stopping conditionitem.x <= parentitem.x >= parent
delete: choice of childthe larger: j++ if [j] < [j+1]the smaller: j++ if [j] > [j+1]
delete: stopping conditiontemp.x >= [j]temp.x <= [j]

If the name of the routine is changed and the less-than and greater-than signs are reversed, the min heap is written. Table 13.9 collects the three lines that change. These two routines were tried with the values 20, 5, 30, 10, 40. After the insertions the array became, in turn, 20; 5, 20; 5, 20, 30; 5, 10, 30, 20; 5, 10, 30, 20, 40. The removal calls returned 5, 10, 20, 30, 40, that is, increasing order.

Another way to reverse the comparisons is to leave the max heap untouched and multiply the priorities by minus one. The largest −x is the smallest x. This trick is used in practice, but it is limited to cases where the key is a number, and it risks overflow at boundary values such as INT_MIN. A more general solution is to move the comparison into a separate function: the routines call that function, and which kind of heap it is gets determined by it. The qsort of the standard library likewise receives the sort direction through such a comparison function.

13.5.3Items whose priority changes

Let us return to the airport example. The fuel of an aircraft is not measured once, at the moment it first contacts the tower, and then forgotten. Every aircraft burns fuel at a different rate. One aircraft may burn 10 gallons (37.85 liters) in a second, while another might fly an hour on 10 gallons. Priorities therefore change over time. In the system an interrupt arrives every second and the fuel levels are updated. Capturing the problem well requires including this change in the model.

When the priority of an item changes, the heap property can break only around that item. In a max heap, an item whose priority increases may become larger than its parent; it is sifted up. An item whose priority decreases may become smaller than its children; it is sifted down. Both operations work along a single root-to-leaf path and take O(lg n). The slides give the sift-up version:

/* priority of the item at k rose: sift it up */
void increase_key(int k, int key) {
  element e = heap[k];
  e.x = key;
  while (k != 1 && e.x > heap[k / 2].x) {
    heap[k] = heap[k / 2];
    k /= 2;
  }
  heap[k] = e;
}

The routine copies the item at position k into e and sets its priority to the new value. Then it runs the same loop as the insertion routine, except that the starting position is k, not n + 1. The condition k != 1 stops at the root; the condition e.x > heap[k / 2].x continues as long as the parent is smaller. At the end of the loop the item is written to its new place. The routine assumes that the new value is larger than the old one. If it is called with a smaller value, the loop does not run at all and the item just shrinks in place; this may break the heap property downward.

When a priority decreases, sifting down is needed. This version is not in the slides; it is obtained by starting the loop of the deletion routine at position k:

/* priority of the item at k fell: sift it down */
void decrease_key(int k, int key) {
  element e = heap[k];
  e.x = key;
  int j = 2 * k;
  while (j <= n) {
    if (j < n && heap[j].x < heap[j + 1].x) j++;
    if (e.x >= heap[j].x) break;
    heap[k] = heap[j];
    k = j; j *= 2;
  }
  heap[k] = e;
}
Example 13.3

Let the heap be 30, 15, 28, 11, 14, 3, 6, 10, 9. The priority of the 9 at position 9 is raised to 31: increase_key(9, 31). Its parent is the 11 at position 4, and 31 > 11; 11 moves down. Then the 15 at position 2 and the 30 at the root move down too. 31 is written at the root. The result is 31, 30, 28, 15, 14, 3, 6, 10, 11; the path is 9 → 4 → 2 → 1, three shifts.

In the same initial heap, the priority of the root is lowered to 5: decrease_key(1, 5). The children of the root are 15 and 28; 28 moves up. The children of position 3 are 3 and 6; 6 moves up. Position 7 is a leaf; 5 is written there. The result is 28, 15, 6, 11, 14, 3, 5, 10, 9. Both results were checked with is_heap and found valid.

The hard part of these routines is not the code but knowing k. The tower knows the name of the aircraft whose fuel changed; it does not know its position in the heap. Searching for an item in a heap takes O(n), because a heap is not a search structure. If a search is made for every update, the gain of the O(lg n) sift is lost. The solution is to keep the position of every item in the heap in a separate index table, for example pos[plane_id]. Every time a heap routine moves an item, it updates this table as well. If an item is moved with heap[i] = heap[j], then pos[heap[i].id] = i is written right after. This way the position is found in O(1) and changing a priority really takes O(lg n). The decrease-key operation of graph algorithms is done the same way in a min heap.

13.6Comparison with other structures

Both operations of the heap take O(lg n). Is that a good result? Could a simpler structure, an array or a list, not do the same job more easily? This section compares five implementations, first by their theoretical costs, then in numbers, and finally in a real measurement.

13.6.1The cost of five implementations

Table 13.10: Five implementations of a max priority queue.
#StructureInsertDelete (largest)Why
1Unsorted arrayΘ(1)Θ(n)Insert at the end; finding the largest means scanning everything.
2Unsorted listΘ(1)Θ(n)Insert at the head; again every node is traversed.
3Sorted array (ascending)O(n)Θ(1)binsearch O(lg n) + n shifts; the largest is at the end.
4Sorted linked list (descending)O(n)Θ(1)Find the place; delete from the head and update the head.
5Max heapO(lg n)O(lg n)Only one root-to-leaf path.

Table 13.10 gives the comparison from the slides. The rows can be taken one at a time.

Unsorted array. The new item is written at the end of the array: one assignment, Θ(1). To remove the largest item, it must first be found. Because the array is unsorted, all items are examined; this is always n − 1 comparisons, and Θ(n). When the item found is removed, the last item is moved into the gap; no shifting is needed. Removal therefore takes exactly linear time.

Unsorted list. In a linked list, the new item is added at the head: one node is allocated and two pointers are updated, Θ(1). Finding the largest again requires traversing all nodes: Θ(n).

Sorted array. If the array is kept in ascending order, the largest item is at the end and removal is Θ(1): n is decremented. Insertion, however, is expensive. The place of the new item is found by binary search (binsearch) in O(lg n), but all items larger than it must be shifted one place to the right. If the new item is the smallest, n shifts are made. If the new item is the largest, no shift is made at all; so insertion is O(n), not Θ(n). If binary search is not used and the place is found by linear search from the start, the situation changes. Finding the place examines k items, and then n − k items are shifted; the total is always about n. Then insertion is Θ(n), not just O(n).

Sorted linked list. If the list is kept in descending order, the largest item is at the head. Removal means taking out the head node and updating the head: Θ(1). In insertion, the place of the new item is found by traversing from the head; no shifting is needed, but binary search cannot be done on a linked list. If the new item is the largest, it is added at the head at once; if it is the smallest, the whole list is traversed. Insertion is therefore O(n).

Max heap. Both operations work along a single root-to-leaf path: O(lg n).

The pattern of the table is clear. Each simple structure makes one of the operations very cheap, but pays for it in the other. Unsorted structures keep insertion cheap because they maintain no order; the price is searching for the largest again every time. Sorted structures keep removal cheap because they maintain a full order; the price is rebuilding that order at every insertion. The heap stands between the two. It does not sort completely; it maintains only a weak order, “every parent is larger than its children”. This order is enough to keep the largest at the root, and repairing it requires work along only one path.

Another idea that comes to mind is to keep the largest value in a separate variable max. In addition to the unsorted array, this variable is updated at every insertion, and looking at the largest becomes O(1). But what happens when the largest item is removed, that is, when that aircraft lands? To find the new largest, the whole array must be scanned again. To avoid this one would have to keep the second largest, and for that the third as well; this is no different from using a sorted array.

13.6.2In numbers: n = 2,000,000

The cost table becomes concrete with a number. Let n = 2,000,000 items, and let every basic operation take one second. This assumption is exaggerated, but it makes the ratios easy to see. lg 2,000,000 ≈ 20.9; it is rounded to 21. That is also why 2 million was chosen: its logarithm is easy to compute, since 221 = 2,097,152.

Table 13.11: Number of steps per operation in the worst case for n = 2,000,000 (one step = one second, by assumption).
StructureInsertDelete
1 · unsorted array12,000,000
2 · unsorted list12,000,000
3 · sorted array2,000,0001
4 · sorted list2,000,0001
5 · max heap≈ 21≈ 21

Table 13.11 compares the five approaches by analysis alone, without writing any code. In the first four structures, one of the operations takes 2 million seconds, about 23 days. In the heap both operations take about 21 seconds. Since a queue performs insertions and removals in roughly equal numbers, looking at the sum of one insertion and one removal is a fair measure. For the simple structures this sum is about 2 million steps; for the heap it is 42 steps. The heap is about 48,000 times faster. By way of analogy: running a program built on a heap forty thousand times takes less time than running it once with one of the other structures.

A real instruction takes not a second but a small fraction of a microsecond. One may therefore raise this objection: “An aircraft arrives at the airport every half hour; even with a queue of a thousand aircraft, the worst structure runs in the blink of an eye. Who will notice that the algorithm is bad?” For a small problem this may be true. But when the same code is part of an operating system, it is called thousands of times a second and the difference spreads through the whole system. In work that demands expertise, a solution that collapses when the workload grows has no academic or scientific value.

13.6.3Measurement

The theoretical comparison was also tested with a measurement. Three implementations were written in C and compiled with -O2: an unsorted array, a sorted array with linear shifting, and a max heap. Into each, n random values were inserted, and then the largest was removed n times. The sums of the values returned by the three structures came out equal in every run; that is, all three returned the same items. Table 13.12 gives the ranges of values over three runs. The values vary from machine to machine; what matters is the shape of the growth.

Table 13.12: Time for n insertions + n removals (seconds; three runs; varies by machine).
nUnsorted arraySorted arrayMax heap
10,0000.12–0.160.011–0.015≈ 0.001
50,0003.3–3.60.57–0.770.008–0.019
100,00016.0–17.12.3–2.90.017–0.027

When n grew tenfold, the time of the unsorted and sorted arrays grew about a hundredfold. This is quadratic growth: when each of n operations takes Θ(n), the total is Θ(n2). The heap's time grows roughly as n lg n. At one hundred thousand items the heap is about 700 times faster than the unsorted array and about 100 times faster than the sorted array. That the sorted array comes out faster than the unsorted array is instructive as well. Both do Θ(n2) total work. But shifting is a very simple loop over consecutive memory cells; between two methods of the same growth class, the constant factor can differ this much. The asymptotic class, however, is stronger than the constant factor: as n grows, the gap to the heap keeps widening.

13.6.4Advanced heaps

The structure described in these notes is the binary heap. There are other, more advanced kinds of heaps that do some operations even faster. Researchers did not think lg n was enough. As in the Olympic motto: Citius! Altius! Fortius! (Faster! Higher! Stronger!) Table 13.13 compares three structures by their min heap operations.

Table 13.13: Operation costs of binary, binomial and Fibonacci heaps. * Fibonacci heap times are amortized.
OperationBinary heapBinomial heapFibonacci heap*
insertO(lg n)O(lg n)O(1)
find minimumO(1)O(lg n)O(1)
delete minimumO(lg n)O(lg n)O(lg n)
decrease keyO(lg n)O(lg n)O(1)
merge two heapsO(n)O(lg n)O(1)

A binomial heap is not a tree but a forest made up of trees of particular sizes. Its main gain is merging: two binomial heaps can be merged in O(lg n). In a binary heap, merging means concatenating two arrays and rebuilding the heap, which takes O(n). The Fibonacci heap postpones the work even further. During insertion and decrease-key it does not tidy the structure; it leaves the tidying to the moment when the minimum is deleted. That is why its times are amortized: a single operation may be expensive, but when the total cost of a sequence of operations is divided by the number of operations, the values in the table result. In graph algorithms that perform many decrease-key operations, such as Dijkstra and Prim, the Fibonacci heap gives a theoretical gain. In practice, the simplicity of the binary heap and its cache-friendly layout in an array often give faster results.

13.7Bottom-up heap construction

Sometimes the items do not arrive one by one; all of them are ready in an array from the start. Heap sort, for example, takes the array to be sorted all at once. The first way that comes to mind to turn such an array into a heap is to insert the items one by one into an empty heap. Since each insertion takes O(lg n), this way takes O(n lg n). There is a better way: fixing the array in place, from the bottom up. This method is called bottom-up heap construction (heapify) and takes O(n).

13.7.1build_heap

The starting point of the idea is the leaves. A tree consisting of a single node is already a heap; it has no children to compare with. In an array of n items, all nodes with k > ⌊n/2⌋ are leaves, because their left children would be at position 2k > n. So the second half of the array, before anything has been done, consists of one-item heaps.

Now we go backward from k = ⌊n/2⌋ toward the root. For each k, the two subtrees of the node are already heaps, because all nodes with larger indices have been fixed earlier. In that case only the item at k may be out of place. This is exactly the situation in deletion: an item whose place is sought at the root, and two heaps. The item at k is sifted down, and the subtree rooted at k becomes a heap. When the loop reaches the root, the whole array is a heap.

void build_heap(element a[], int n) {
  for (int k = n / 2; k >= 1; k--) {
    element temp = a[k];
    int i = k, j = 2 * k;
    while (j <= n) {
      if (j < n && a[j].x < a[j + 1].x) j++;
      if (temp.x >= a[j].x) break;
      a[i] = a[j];
      i = j; j *= 2;
    }
    a[i] = temp;
  }
}

The outer loop counts backward from k = n / 2 down to 1. The inner part is the same as the loop in delete_max_heap; the only difference is that the starting position is k rather than 1. In Horowitz's book this inner loop is a separate routine called adjust. temp holds the item at k; i marks the hole and j the children. As long as the larger child is larger than temp, it is moved up and the hole moves down. At the end temp is written into the hole.

The routine uses no extra array; the heap is built inside the input array. Its extra memory is therefore O(1). Such algorithms are called in-place algorithms. The array is 1-based: the items run from a[1] to a[n] and a[0] is unused. The caller must supply an array of at least n + 1 cells.

13.7.2Code trace: build_heap(a, 7)

The input is 5, 3, 8, 9, 1, 12, 7 and is not yet a heap; the 5 at the root is smaller than its children. n = 7, ⌊n/2⌋ = 3. Positions 4, 5, 6 and 7 are leaves. The outer loop runs for 3, 2 and 1. Table 13.14 summarizes the inner loop for each k.

Table 13.14: Trace of build_heap(a, 7).
ktempStepsPosition where it settleda[1..7] (after)
——input—5, 3, 8, 9, 1, 12, 7
38children 12 and 7, the larger is a[6] = 12; 8 < 12: 12 moves up; j = 12 > n65, 3, 12, 9, 1, 8, 7
23children 9 and 1, the larger is a[4] = 9; 3 < 9: 9 moves up; j = 8 > n45, 9, 12, 3, 1, 8, 7
15children 9 and 12, the larger is a[3] = 12; 5 < 12: 12 moves up. Children 8 and 7, the larger is a[6] = 8; 5 < 8: 8 moves up; j = 12 > n612, 9, 8, 3, 1, 5, 7
5132839415126770–152338495161277build_heap(a, 7) 513212394158677i0–152331249516877▲ k▲ ibuild_heap(a, 7)k = 3 519212334158677i0–152931243516877▲ k▲ ibuild_heap(a, 7)k = 2 1219283341556770–112293843516577build_heap(a, 7)
Figure 13.13: Four moments of build_heap. From top to bottom: the input; the end of the steps k = 3, k = 2 and k = 1. Green nodes are roots whose own subtrees are already heaps.

At k = 3, 8 looks as if it swapped places with 12; in fact 12 was moved up and 8 was written into the hole. The subtree rooted at 3 is now 12, 8, 7. At k = 2, similarly, 9 moves up and 3 sinks to a leaf. After both subtrees are heaps, the root is fixed at k = 1. This time the path of 5 is two levels: first 12, then 8 moves up, and 5 settles at position 6. The outer loop ends at k = 0. The result 12, 9, 8, 3, 1, 5, 7 is a valid max heap. In all, the routine made 4 moves and, for each k, one final write, that is, 3 final writes.

If the same seven values had been inserted one by one into an empty heap with insert_max_heap, the result would have been 12, 8, 9, 3, 1, 5, 7. This is also a valid max heap, but it differs from what build_heap gives. A given set of values has more than one heap; the two methods arrive at different ones. Which one is obtained does not matter. In both the root is the largest item, and subsequent removals give the same order.

13.7.3Why O(n)?

At first glance the cost of build_heap can be computed as follows: the outer loop runs n/2 times, and each time the inner loop takes O(lg n); the total is O(n lg n). This bound is correct but loose. The key observation is that the great majority of nodes are in the lower part of the tree, and the nodes there can sink only very little.

level 0 (root)1 node × at most 3 steps = 3level 12 nodes × at most 2 steps = 4level 24 nodes × at most 1 step = 4level 3 (leaves)8 nodes × at most 0 steps = 0
Figure 13.14: Maximum number of levels each node can sink, by level, in a complete tree with 15 nodes. The root can sink 3 levels; the leaves never sink.

A node can sink at most as many levels as there are below it. This number is called the height of the node; the height of a leaf is 0. About half of the nodes are leaves and never sink. A quarter are directly above the leaves and sink at most 1 level. An eighth sink at most 2 levels. Only a single node, the root, can sink ⌊lg n⌋ levels. Figure 13.14 does this computation for a complete tree with 15 nodes: 0 · 8 + 1 · 4 + 2 · 2 + 3 · 1 = 11. The total number of sinking steps is at most 11, and this number is smaller than n = 15.

Theorem 13.3 (Cost of bottom-up construction)

build_heap turns an array of n items into a max heap in O(n) time. The total number of sinking steps is less than n.

Proof. In a heap of n items, the number of nodes of height h is at most ⌈n / 2h+1⌉. Sifting down a node of height h takes at most h rounds, and each round does constant work. The total work is bounded as follows:

Σh ≥ 0 ⌈n / 2h+1⌉ · O(h) = O(n · Σh ≥ 0 h / 2h) = O(2n) = O(n)

Here Σ h / 2h = 1/2 + 2/4 + 3/8 + … = 2. The value of this sum can be seen as follows. Let S = Σh ≥ 1 h / 2h. Then S / 2 = Σh ≥ 1 h / 2h+1 = Σh ≥ 2 (h − 1) / 2h. Subtracting gives S − S/2 = 1/2 + Σh ≥ 2 1/2h = 1/2 + 1/2 = 1, so S = 2. A more exact count is possible for a full tree: in a perfect tree with 2m − 1 nodes, the total number of sinking steps is at most n − m, that is, less than n. In the 15-node example this is 15 − 4 = 11. ∎

Why does repeated insertion not give the same cheapness? In insertion the movement is upward, and the number of levels a node can climb is its depth, that is, its distance from the root. Half of the nodes are on the bottom level, and each of them can climb ⌊lg n⌋ levels to the root. The crowded lower levels can walk the longest path; the total reaches Θ(n lg n). In bottom-up construction the situation is reversed: only the few nodes near the top walk the long path.

The two methods were compared in a measurement. On random arrays, the numbers of comparisons and moves made by build_heap were counted, and the same values were also inserted one by one. Table 13.15 gives the results.

Table 13.15: Counts for bottom-up construction and for repeated insertion. The last column is the number of shifts in insertion in increasing order (the worst case).
nbuild_heap comparisonsbuild_heap movesInsertion (random) shiftsInsertion (increasing) shifts
1,0001,8937621,3377,987
10,00018,8417,46012,898113,631
100,000188,06974,406128,1221,468,946
1,000,0001,881,022743,3381,279,94217,951,445
10,000,00018,815,2357,441,05712,817,582213,222,809

The counts of build_heap grow exactly in proportion to n: about 1.88n comparisons and about 0.74n moves. The number of shifts in insertion in increasing order, in contrast, grows by more than a factor of ten when n grows tenfold; there are 8 shifts per item at a thousand items and 21 per item at ten million. This is n lg n growth. The average for insertion in random order stays at about 1.3 shifts per item, but this average is not a guarantee. build_heap, on the other hand, makes fewer than n moves on every input. At ten million items, the times of both methods were measured at around 0.1 seconds on this machine (build_heap 0.09–0.12 s, random insertion 0.13–0.15 s).

13.8d-ary heap

In a binary heap every node has at most two children. This number does not have to be 2. A heap can also be built on a complete tree in which every node has at most d children.

Definition 13.4

A d-ary heap is a tree in which every node has at most d children, every level except the last is full, and the last level fills from left to right; the value of every node is not smaller than those of its children (the max version). d = 2 gives the binary heap.

95060180270320450530675740810965102511
Figure 13.15: A 3-ary max heap with 12 items. Indices start at 0; the children of node i are 3i + 1, 3i + 2, 3i + 3.

A d-ary heap is also stored in an array. In a 0-based array, the children of node i run from d · i + 1 to d · i + d, and its parent is ⌊(i − 1)/d⌋. For d = 2 these formulas are the same as those of the 0-based binary heap. Figure 13.15 shows a 3-ary heap. The children of the root, 95, are 60, 80 and 70 at indices 1, 2 and 3. The children of the 80 at index 2 run from 3 · 2 + 1 = 7 to 9: 75, 40 and 10. The 70 at index 3 has only two children, at indices 10 and 11: 65 and 25. The tree is complete; the last level fills from left to right.

Table 13.16: The binary heap and the d-ary heap (0-based array).
Binary (d = 2)d-ary
parent(i - 1) / 2(i - 1) / d
children2i + 1, 2i + 2d·i + 1 … d·i + d
height≈ lg n≈ logd n
insert / change a key toward the rootO(lg n)O(logd n): faster
delete the rootO(lg n)O(d · logd n): d children are compared

As the number of children grows, the tree becomes shallower: the height drops from lg n to logd n = lg n / lg d. For example, with a million items the height of a binary heap is 19, and that of a 4-ary heap is about 10. Since sifting up makes only one comparison per level, insertion becomes faster. Sifting down, however, must find the largest of d children at every level; this takes d − 1 comparisons. Deleting the root therefore takes O(d · logd n) and gets slower as d grows.

Because the table in the slides speaks of a max heap, it calls the operation that requires sifting up “increase key”. In a min heap the same operation is “decrease key”. Dijkstra's shortest-path algorithm uses a min heap and performs many decrease-key operations and relatively few deletions. In dense graphs, where the number of edges is large compared with the number of vertices, this ratio is pronounced. In such cases choosing d > 2 pays off. A shallow tree also has the advantage of being cache-friendly: the d children of a node sit side by side in the array and often fall on the same cache line.

13.9Applications and heap sort

A priority queue is used wherever the question “which is the next most important job?” is asked again and again. The slides list six areas.

  • Operating systems. Scheduling of processes and interrupts, timer events. The timer that will expire soonest sits at the root of a min heap.
  • Graph algorithms. Dijkstra's shortest-path algorithm and Prim's minimum spanning tree algorithm choose, at every step, the nearest vertex not yet processed. This choice is made with a min heap.
  • Heap sort. Build a heap, then remove the root n times: O(n lg n), in-place sorting.
  • Event simulation. Events are drawn from a min heap according to their timestamps; each event may add new future events.
  • The largest or smallest k items. In a stream of data, the largest k items are tracked with a min heap of size k. If a new value is larger than the root, the root is discarded and the new value is inserted. Each step takes O(lg k) and the whole stream takes O(n lg k). For the smallest k items the same job is done with a max heap.
  • Huffman coding. In text compression, the two trees with the smallest frequencies are merged repeatedly. Finding the two smallest at every step is a job for a min heap.

The shortest of these applications is heap sort, and it brings together all the pieces examined in the notes. We saw that repeated removal yields decreasing order. To apply this idea without an extra array, one observation suffices: when the root is removed, the heap shrinks by one item and a cell at the end of the array becomes free. The largest item that was removed can be placed in exactly that cell. The end of the array thus becomes the region where the sorted items accumulate. The following routine applies this idea:

/* sorts a[1..n] in ascending order; no extra array */
void heap_sort(element a[], int n) {
  build_heap(a, n);                /* O(n) */
  for (int m = n; m > 1; m--) {
    element temp = a[m];           /* last item */
    a[m] = a[1];                   /* largest to the end */
    int i = 1, j = 2;              /* fix a[1..m-1] */
    while (j <= m - 1) {
      if (j < m - 1 && a[j].x < a[j + 1].x) j++;
      if (temp.x >= a[j].x) break;
      a[i] = a[j];
      i = j; j *= 2;
    }
    a[i] = temp;
  }
}

The routine first turns the array into a heap with build_heap. Then m, the current size of the heap, goes down from n to 2. In each round the last item is taken into temp, the largest item at the root is written to a[m], and a place for temp is sought within a[1..m-1] starting from the root. This last part is the loop of delete_max_heap; only the end of the heap is m - 1. When the loop ends, a[2..n] is sorted and the smallest item is in a[1].

The array 5, 3, 8, 9, 1, 12, 7 was sorted by this routine into 1, 3, 5, 7, 8, 9, 12. The routine was also tested with 3000 random arrays of 0–149 items containing duplicate values, and gave increasing order every time. The cost is the sum of O(n) for build_heap and O(n lg n) for the n − 1 sift-downs: O(n lg n). This time bound holds in the worst case too. The extra memory is only a few variables: O(1).

13.10Complexity summary

Table 13.17: Cost of operations in a binary heap with n items.
OperationTimeExtra memoryComment
look at the largestO(1)O(1)heap[1]
insertΩ(1) … O(lg n)O(1)sift up
remove the largestO(lg n)O(1)sift down
change a priorityO(lg n)O(1)if the position is known
bottom-up constructionO(n)O(1)in place
build by n insertionsO(n lg n)O(1)worst case: increasing order
heap sortO(n lg n)O(1)in place
search for an arbitrary itemO(n)O(1)a heap is not a search structure

Table 13.17 collects the operations examined in the notes. The table has a common rationale: in a heap the work is bounded by the length of a root-to-leaf path, and by Theorem 13.2 this length is ⌊lg n⌋. Looking at the largest requires no walking along a path. Bottom-up construction is linear because most paths are short. Search cannot exploit the heap property: if the sought value is smaller than the root, it may be in any subtree. The extra memory is constant in every row, because the heap is the array itself and the routines use only a few index variables.

13.11Common mistakes

  1. Mixing up the 1-based and 0-based formulas. In a 1-based array the parent is i/2 and the children are 2i and 2i+1; in a 0-based array the parent is (i−1)/2 and the children are 2i+1 and 2i+2. If they are mixed up, the wrong nodes are compared and the heap silently breaks.
  2. Declaring the array one smaller than the capacity. With element heap[MAX_ELEMENTS - 1], the 199th item is written to heap[199], outside the array.
  3. Writing return 0; in a routine that returns element. An integer does not convert to a structure; it is a compile error. Success is returned as a bool and the item through a pointer parameter.
  4. Forgetting the j < n test and reading heap[j+1]. The cell read is outside the heap; in build_heap it may even be outside the array.
  5. Choosing the first child instead of the larger child in deletion. When the smaller child moves up, it becomes the parent of its larger sibling and the heap property breaks.
  6. Taking a heap for a sorted array or a binary search tree. Only heap[1] is guaranteed to be the largest; there is no order among siblings, and searching a heap takes O(n).
  7. Not stopping the insertion loop at the root. If i >= 1 is written instead of the condition i != 1, heap[0] is read and the new item may be written outside the heap.
  8. Sifting in the wrong direction when a priority changes. In a max heap, an item whose priority rises is sifted up and one whose priority falls is sifted down. Calling increase_key with a smaller value may break the heap.

13.12Exam-style question

Example 13.4

Into a max heap with heap[1..6] = 14, 12, 7, 10, 8, 6 initially, 15, 109, 107, 3, 15 are inserted in turn; then delete_max_heap is called twice. (i) What are the contents of the array after the insertions? (ii) What are the removed items and the final array? (iii) Which insertion made the fewest shifts and which the most?

(i) The five insertions were traced step by step in Table 13.4. The final array is 109, 107, 14, 15, 15, 6, 7, 10, 12, 3, 8, n = 11. In an exam it is enough to write the path of each insertion: the new position n + 1, then comparison with the parent and, if needed, a climb to the parent.

(ii) The first removal returns the 109 at the root. The last item is the 8 at position 11; n drops to 10. The children of the root are 107 and 14; 107 moves up to the root and the hole moves down to 2. The children of 2 are the two 15s at positions 4 and 5. Since the left child is not smaller than the right one, j stays at 4; since 8 < 15, the 15 at position 4 moves up and the hole moves down to 4. The children of 4 are 10 and 12; 12 is larger and 8 < 12, so 12 moves up and the hole moves down to 9. The left child of 9 would be at position 18; 18 > 10. 8 is written at position 9. The array becomes 107, 15, 14, 12, 15, 6, 7, 10, 8, 3.

The second removal returns 107. The last item is the 3 at position 10; n drops to 9. The children of the root are 15 and 14; 15 moves up to the root and the hole moves down to 2. The children of 2 are 12 and 15; the right one is larger, 15 moves up, and the hole moves down to 5. The left child of 5 would be at position 10, and 10 > 9; 3 is written at position 5. The removed items are 109 and 107; the final array is 15, 15, 14, 12, 3, 6, 7, 10, 8, n = 9.

(iii) The insertion of 3 made no shift: its parent was not smaller than 8. This is the best case, Ω(1). 109 climbed all the way to the root and made 3 shifts; in a heap of 8 items this is the worst case, equal to the height, O(lg n). All arrays in this solution are identical to the output of a test program that uses the code in the slides verbatim.

13.13Exercises and solutions

The six exercises of the slides are given here with their solutions. The arrays in the solutions were verified with test programs.

13.13.1Five insertions into an empty heap

Question. If 20, 5, 30, 10, 40 are inserted into an empty max heap, what is the array after each insertion?

Solution. 20 is written at the root: 20. 5 goes to position 2 and its parent is smaller than 20: 20, 5. 30 goes to position 3; its parent is smaller than 30, so 20 moves down and 30 climbs to the root: 30, 5, 20. 10 goes to position 4; its parent, the 5 at position 2, is smaller, so 5 moves down; its new parent is larger than 10 (it is 30), and 10 stops at position 2: 30, 10, 20, 5. 40 goes to position 5; its parent is smaller than 40, as is the next one, and it climbs to the root: 40, 30, 20, 5, 10.

13.13.2Deletion for a min heap

Question. If delete_max_heap is rewritten for a min heap, which lines change?

Solution. The name of the routine becomes delete_min_heap. In choosing the child, the smaller child is sought: if (j < n && heap[j].x > heap[j + 1].x) j++;. The stopping condition becomes if (temp.x <= heap[j].x) break;. Everything else is the same. The full code is given in 13.5.2.

13.13.3Insertion into a heap of a thousand items

Question. In a heap with n = 1000 items, how many shifts can an insertion make at most?

Solution. The number of levels of a complete binary tree with 1000 items is ⌈lg 1001⌉ = 10: 29 = 512 ≤ 1000 < 1024. Between a leaf and the root there are at most 9 edges. An item that climbs from the leaf level to the root makes one shift per edge; at most 9 shifts, that is, ⌊lg 1000⌋ = 9. If the new item goes to position 1001, the path is 1001 → 500 → 250 → 125 → 62 → 31 → 15 → 7 → 3 → 1, and it really is 9 edges.

13.13.4The relatives of node 13

Question. In a 1-based heap, at which indices are the parent and children of node 13?

Solution. The parent is ⌊13/2⌋ = 6. The children are 2 · 13 = 26 and 27; they exist only if the heap has enough items (n ≥ 26 for the left child, n ≥ 27 for the right child). The detailed computation is in Example 13.1.

13.13.5Construction versus repeated insertion

Question. If repeated insert is applied to the array 5, 3, 8, 9, 1, 12, 7 instead of build_heap, is the result the same?

Solution. No. build_heap gives 12, 9, 8, 3, 1, 5, 7. Repeated insertion proceeds as follows: 5; 5, 3; 8, 3, 5; 9, 8, 5, 3; 9, 8, 5, 3, 1; 12, 8, 9, 3, 1, 5; 12, 8, 9, 3, 1, 5, 7. Both results are valid max heaps, but they differ. The same set of values has more than one heap arrangement.

13.13.6Where is the smallest item?

Question. Where can the smallest item of a max heap be? What does it cost to find it?

Solution. If the values are distinct, the smallest item can be only at a leaf. A node with a child is larger than at least one value, its child, by the heap property; it cannot be the smallest. The leaves are the indices from ⌊n/2⌋ + 1 to n. If there are duplicate values, the smallest value may also be found at an internal node, but a copy of that value is certainly at a leaf as well. In both cases it suffices to scan the leaves. There are about n/2 leaves and all of them must be examined, because there is no order among the leaves. The cost is Θ(n). A heap makes finding the largest O(1), but does not speed up finding the smallest.

13.14Summary

  • A priority queue is a queue in which the first item to remove is determined by priority rather than arrival order: in the max version the item with the highest value is removed first, in the min version the item with the lowest value.
  • As an abstract data type it has insert, remove and peek operations; it can be implemented with an unsorted or sorted array, a list, or a heap.
  • A heap is the combination of a complete binary tree and the rule “parent ≥ child”. In a 1-based array the parent is i/2 and the children are 2i and 2i+1; no pointers are needed.
  • A heap is not a binary search tree; there is no order among siblings. Only the root is guaranteed to be the largest.
  • Insertion: the first empty position is opened, larger ancestors are shifted down one level each, and the item is written once at the end. Best case Ω(1), worst case O(lg n).
  • Deletion: the root is taken, a place is sought for the last item starting from the root, and larger children are moved up: O(lg n). The test j < n checks that the right child exists.
  • The height of a complete binary tree is ⌊lg n⌋; this is why heap operations are logarithmic.
  • Using a structure instead of a global array allows multiple heaps and a capacity chosen at run time. For a min heap the comparisons are reversed. An item whose priority changes is sifted up or down in O(lg n) if its position is known.
  • Simple structures push one of the operations to Θ(n); a heap keeps both logarithmic. In the measurement, at a hundred thousand items the heap came out about 700 times faster than the unsorted array.
  • Bottom-up construction turns an array into a heap in place and in O(n) time; repeated insertion takes O(n lg n) in the worst case.
  • The d-ary heap makes the tree shallower and speeds up insertion; binomial and Fibonacci heaps speed up merging and decrease-key. Heap sort is the application of the priority queue to sorting: O(n lg n), in place.

13.15Key terms

  • priority queue
  • abstract data type (ADT)
  • key
  • complete binary tree
  • parent
  • level
  • height
  • heap
  • max-heap
  • min-heap
  • binary search tree
  • up-heap (sifting up)
  • down-heap (sifting down)
  • bottom-up heap construction (heapify)
  • decrease key
  • Fibonacci heap
  • heap sort
  • in-place sort
  • amortized analysis
  • cache
  • heap memory

13.16Test Yourself

  1. The values 4, 9, 2, 7, 11 are inserted in turn into an empty max heap. What is the final array? How many shifts are made?

    Answer

    Arrays: 4; 9, 4; 9, 4, 2; 9, 7, 2, 4; 11, 9, 2, 4, 7. Shifts: 1 for 9 (4 moves down), 0 for 2, 1 for 7 (4 moves down), 2 for 11 (7 and 9 move down); 4 in total.

  2. delete_max_heap is called once on the heap 50, 30, 40, 10, 20, 35. What are the removed item and the new array?

    Answer

    50 is removed. The last item, 35, is taken out, n = 5. The children of the root are 30 and 40; 40 moves up to the root and the hole moves down to 3. The left child of 3 would be at position 6, but 6 > 5. 35 is written at position 3: 40, 30, 35, 10, 20.

  3. In a 1-based heap of 100 items, what are the parent, the children and the level of node 37?

    Answer

    The parent is ⌊37/2⌋ = 18 and the children are 74 and 75 (both ≤ 100, so they exist). The level is ⌊lg 37⌋ = 5, because 32 ≤ 37 < 64.

  4. What does build_heap turn the array 1, 2, 3, 4, 5, 6, 7 into? How many moves are made?

    Answer

    k = 3: the children of 3 are 6 and 7; 7 moves up, 3 moves down. k = 2: the children of 2 are 4 and 5; 5 moves up, 2 moves down. k = 1: the children of the root are 5 and 7; 7 moves up; then, between 6 and 3, 6 moves up; 1 sinks to position 6. The result is 7, 5, 6, 4, 2, 1, 3; 4 moves.

  5. The value 2 is inserted into the min heap 3, 6, 7, 14, 8, 12, 15. What are the path and the final array?

    Answer

    The new position is 8. The ancestors are 14 (position 4), 6 (position 2) and 3 (the root); since 2 is smaller than all of them, all three move down. The path is 8 → 4 → 2 → 1, 3 shifts. The final array is 2, 3, 7, 6, 8, 12, 15, 14.

  6. At which indices can the second and third largest items be in a max heap with distinct values?

    Answer

    The parent of the second largest item can only be the root, because its parent must be larger than it and the only item larger than it is the root: index 2 or 3. The parent of the third largest item is the root or the second largest: index 2, 3, or one of the children of the second largest, that is, one of 4, 5, 6, 7.

  7. A new item is inserted into a max heap of 31 items. What is the most shifts that can be made? The fewest?

    Answer

    The new item goes to position 32; this is the first position of a new level. The path is 32 → 16 → 8 → 4 → 2 → 1, so at most ⌊lg 32⌋ = 5 shifts. If the new item is smaller than or equal to its parent at position 16, no shift is made: at least 0.

  8. In a 0-based 3-ary heap, at which indices are the parent and children of node 5?

    Answer

    The parent is ⌊(5 − 1)/3⌋ = 1. The children are 3 · 5 + 1 = 16, 17 and 18.

  9. A million items will first be inserted into a priority queue, and then only the ten largest will be removed. Is an unsorted array or a heap more suitable?

    Answer

    In an unsorted array a million insertions are cheap (each Θ(1)), but each of the ten removals needs about a million comparisons: about ten million in total. For a heap, the items can first be put into an array and turned into a heap with build_heap in fewer than n moves; ten removals need about 10 · 2 · 19 = 380 comparisons. The unsorted array makes about 11 million steps in total and the heap about 2 million (about 1.9n comparisons for construction). The heap is still ahead, but the difference is only about a factor of five, because most of the work is done at the input. As the number of removals grows, the heap's advantage grows.

13.17Further reading

  • E. Horowitz, S. Sahni and S. Anderson-Freed, Fundamentals of Data Structures in C: the source followed in these notes for heaps, the adjust routine and heap sort.
  • T. H. Cormen, C. E. Leiserson, R. L. Rivest and C. Stein, Introduction to Algorithms, Chapter 6: gives the O(n) analysis of heap construction, heap sort and the priority queue operations with proofs; the chapter on Fibonacci heaps is the source of the amortized times.
  • R. Sedgewick, Algorithms in C, Parts 1–4, Chapter 9: describes array, list and heap implementations of the priority queue and the indirect heap that tracks items by index.
  • J. W. J. Williams, “Algorithm 232: Heapsort”, Communications of the ACM 7(6), 1964 and R. W. Floyd, “Algorithm 245: Treesort 3”, Communications of the ACM 7(12), 1964: two short original papers that introduced the binary heap and heap sort and added bottom-up construction.

13.18References

  1. E. Horowitz, S. Sahni, S. Anderson-Freed, Fundamentals of Data Structures in C, Section 5.6 (Heaps), Chapter 7 (Heap Sort).
  2. T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms (CLRS), MIT Press, Chapter 6 (Heapsort, priority queues) and the chapter on Fibonacci heaps.
  3. R. Sedgewick, Algorithms in C, Parts 1–4, Chapter 9 (Priority Queues and Heapsort).
  4. J. W. J. Williams, “Algorithm 232: Heapsort”, Communications of the ACM, 7(6), 347–348, 1964.
  5. R. W. Floyd, “Algorithm 245: Treesort 3”, Communications of the ACM, 7(12), 701, 1964.

Related pages: Chapter 13 slides · © Sercan Külcü. All rights reserved.