DSABook – Binary heaps

9.5 Binary heaps

The binary heap is a data structure that can be used to implement an efficient priority queue. It is organised as a tree that satisfies the heap property and has an additional invariant: it must also be a complete binary tree.

Recall from Section 9.1.1 that a complete binary tree has all levels completely filled except possibly the last, and the last level is filled from left to right. As a result, a complete binary tree with n nodes has exactly one possible shape. Because of this structure, the height h of the tree satisfies: 2^h \le n < 2^{h+1}, which implies that h\in O(\log n). Complete binary trees are therefore balanced, and any operation that linear in the height of the tree runs in O(\log n) time. Using a complete tree has several advantages:

It ensures that the tree remains balanced after adding an element to the tree.
A new element can only be placed in one specific position – the next available spot on the lowest level – so we do not need to decide where to insert it.
The tree can be stored directly in an array, making the implementation simple and space-efficient.

9.5.1 Representing complete binary trees as arrays

Since a complete binary tree has exactly one possible shape for a given number of nodes, we can take advantage of this structure and store it directly in an array. Unlike other binary tree representations, we do not need explicit pointers to parent or child nodes. This leads to a simple and compact implementation of complete binary trees. Instead of pointers, the positions of a node’s parent and children can be determined using simple index calculations.

To represent a complete binary tree in an array, we assign a unique array index to each node according to its position in the tree. The nodes are numbered level by level, starting at the root and proceeding from left to right within each level. The root node is assigned index 0, its left child index 1, its right child index 2, and so on. This systematic numbering ensures that a node’s position in the array directly corresponds to its logical position in the tree. As a result, the indices of a node’s parent and children can be computed easily using simple arithmetic.

An array can store the values of a complete binary tree efficiently by placing each value at the array index corresponding to the node’s position in the tree. If the tree is traversed in breadth-fist order (see Section 9.1.3), the nodes are visited in increasing index order: 0, 1, 2, \ldots, n-1. In other words, the nodes of the tree are stored in the array level by level, with each level appearing consecutively. An example binary heap is shown in Figure 9.7, together with its array representation.

Figure 9.7: An example binary heap together with its array representation. Smaller values indicate higher priority. The node containing the value “28” is highlighted, its parent has the value “17” and the children are “75” and “34”..

You can use simple formulas to compute the array index of a node’s relatives in a complete binary tree with n nodes, given a node at index i:

\begin{align*} \text{parent}(i) &= \lfloor (i - 1)/2 \rfloor & (\text{if~ } & i > 0) \\ \text{left}(i) &= 2i + 1 & (\text{if~ } & 2i + 1 < n) \\ \text{right}(i) &= 2i + 2 & (\text{if~ } & 2i + 2 < n) \end{align*}

For example, the left child of node at position 4 (which contains the value 28) is at index \text{left}(4) = 2 \cdot 4 + 1 = 9 (which contains the value 75).

Here is a practice exercise for calculating the array indices of nodes.

Some course books and implementations put the root in position 1 in the array, and leave the cell at position 0 empty (or use it for temporary values). Doing this changes the arithmetic for calculating the relatives. Beware of this if you happen to read another text about binary heaps!

Here is a practice exercise for calculating the array indices of nodes.

9.5.2 Using dynamic arrays

So, arrays are a compact and efficient representation of complete binary trees. But they cannot change their size, and if we want to implement a priority queue we have to be able to add and remove elements quickly.

Therefore we should not use arrays, but instead dynamic arrays. Recall from Section 6.4 that they are just like arrays, but you can also add elements to the end of the array, and also remove from the end. In our pseudocode below we will assume that we can index them as normal arrays, but they also have special methods addLast and removeLast that grow and shrink the array with one element.

9.5.3 Implementing binary heaps

It is important not to confuse the logical representation of a heap with its physical implementation. Logically, a heap is a tree structure that satisfies the heap property. In practice, however, it is implemented using a dynamic array that represents a complete binary tree.

When describing heap operations, we will usually explain them in terms of tree operations, since this makes the behavior of the algorithms easier to understand conceptually. Nevertheless, it is important to remember that in an actual implementation these operations are carried out using array indices and array updates, rather than explicit tree pointers.

Checking the heap property

To start with, we define a function that verifies that a given binary heap satisfies the heap property:

checkHeapPropery(heap):
    for pos in 1 .. heap.size-1:
        if heap[pos] < heap[parent(pos)]:
            return false
    return true

Note that we start the iteration from position 1: this is because position 0 contains the root of the tree, and the root doesn’t have a parent.

When implementing a data structure, it is often helpful to encode the invariants explicitly and verify them, possibly using assertions, within the various operations. This can make it easier to detect errors and ensure that the data structure remains valid after each modification.

When modifying a data structure that must satisfy an invariant, the goal is to update the structure while ensuring the invariant still holds. In practice, it is often easier to separate these steps: first perform the modification, even if this temporarily breaks the invariant, and then repair the structure to restore it. We will follow this approach when defining the binary heap operations.

Getting the highest-priority element

Since the array satisfies the heap property, the element at index 0 is the root and will always contain the highest-priority element. Therefore it is very efficient to take a little peek into which the next element will be, without modifying the heap. Note that we first need to check that the heap is not empty, because then we will get an error message when trying to access index 0.

9.5.4 Inserting into a heap

We want to be able to add elements to our heap. Since we are using a dynamic array, there is only one place where we can insert a new element: at the end of the array. However, the newly inserted element is not necessarily in the correct position, so the insertion may temporarily violate the heap invariant. We must therefore restore the heap property after adding the new element.

The new element might have higher priority than its parent. If this happens, we swap the new element with its parent. We then repeat the same check from the new position, because the element may still have too high priority to remain there. This process continues until the element either reaches the root or has a parent with higher priority.

Notice that we do not need to compare the new element with its parent’s other child, if there is one. Before the insertion, the heap already satisfied the heap invariant, so the parent had higher priority than both of its children. Therefore, if the new element has higher priority than the parent, it must also have higher priority than the other child. On the other hand, if the new element does not have higher priority than its parent, then it is already in the correct position. So, to restore the heap invariant after insertion, it is enough to compare the new element only with its parent as it moves upward through the heap. This process of moving the value up the tree is often called “bubble-up”, “trickle-up”, “swim-up” or “sift-up”.

Algorithm: Adding to a binary heap

To insert the value v into a heap:

Add v to the end of the heap.
Repeat until v reaches its correct position:
- Compare v with its parent.
- If v has higher priority, swap it with the parent.

Figure 9.8 illustrates how the algorithm works for inserting the value 10 into the heap from Figure 9.7. Note that the heap is shown as a tree, but you should keep in mind that it is actually stored as an array.

Figure 9.8: Inserting 10 into the example heap in Figure 9.7. (a) After inserting 10, we place it at the next free position, shown here as the right child of 43. (b) Since 10 is smaller than its parent 43, the two elements swap positions. (c) The value 10 is still smaller than its new parent 12, so we swap once more. Now 10 has parent 8, which is smaller, so the heap property is restored..

The algorithm above can be translated to pseudocode quite straightforwardly:

add(heap, elem):
    heap.addLast(elem)                 // Add the element to end of the heap.
    pos = heap.size - 1                // This is the position of the new element.
    while pos > 0 and heap[pos] < heap[parent(pos)]:
        swap(heap, pos, parent(pos))   // Swap the element with its parent.
        pos = parent(pos)              // Move up one level in the tree.

Since a heap is a complete binary tree, its height is as small as possible for the number of nodes it contains. A heap with n nodes therefore has height O(\log(n)). Intuitively, this is because each new level in the tree can contain twice as many nodes as the previous level. The ith level contains 2^i nodes, and the first i+1 levels together contain 2^{i+1} - 1 nodes. So the number of levels grows logarithmically with the number of nodes.

Each call to add takes O(\log(n)) time in the worst case. This is because the inserted element can move upward by at most one level at a time. In the worst case, it moves from the last level all the way to the root. Therefore, inserting n values one at a time takes O(n \log(n)) time in the worst case.

Exercise: Insert into a min-heap

9.5.5 Removing from a heap

Heaps are usually used to implement priority queues, where we repeatedly remove the element with the highest priority. This is the next element to be processed, and it is always stored at the root of the heap, at index 0 in the array.

To remove the highest-priority element, we remove the root. However, we cannot simply leave the root empty, since this would violate the requirement that the heap remains a complete binary tree. Instead, we remove the last element in the array, and replace the root with it. This preserves completeness but may violate the heap property.

The new root may now have lower priority than one or both of its children. Therefore we compare it with its children and swap it with the one that has higher priority. It is essential to choose the smaller child – otherwise, the heap property could still be violated after the swap. Once the swap is performed, the element moves down the tree. We repeat the process from the new position, until the element is in its correct place – that is, until it has higher priority than both of its children, or it reaches a leaf. At that point, the heap property is restored. This process is often called “bubble-down”, “trickle-down”, “sink-down” or “sift-down”.

Algorithm: Remove the element with highest priority from a binary heap

To remove the highest-priority element, that is, the root of the heap:

Delete the last element of the heap, and replace the root with it. Let the new root be v.
Repeat until v reaches its correct position:
- Compare v with its highest-priority child.
- If the child has higher priority, swap them.

Figure 9.9 illustrates how the algorithm works for removing the highest-priority value from the final heap in Figure 9.8.

Figure 9.9: Removing the highest-priority element from the final heap in Figure 9.8. (a) We remove the last heap element, 43, and replace the root with it. (b) The smallest child, 10, is smaller than 43, so we swap it with the parent. (c) The smallest child, 12, is smaller than 43, so we swap it with the parent. Now 43 only has larger children, so the heap property is restored..

Note: One common mistake is to forget to replace the root with the last heap element, and instead try to replace the root with its smallest child. (And then “bubble down” the hole of that child.) This approach does not work because the heap must maintain the shape of a complete binary tree. For example, if we use this idea to remove the minimum element from the final heap in Figure 9.9, we would end up with 12 as the root, and 15 as its right child. But 15 would not have any right child, and we no longer have a complete tree.

The complexity of this algorithm is logarithmic, O(\log(n)), of the same reason as adding an element: Since the tree is complete, there are a logarithmic number of levels, and the element travels downward by one level in each iteration. In the worst case, it moves from the root all the way to a leaf.

Here is pseudocode for removing the highest-priority element:

removeMin(heap):
    oldRoot = heap[0]             // Remember the current highest-priority element.
    heap[0] = heap.removeLast()   // Remove the last element from the array,
    pos = 0                       // and put it into the root position.
    child = smallestChild(heap, pos)
    while child is not null and heap[child] < heap[pos]:
        swap(heap, pos, child)             // Swap the element with its smallest child.
        pos = child                        // Move down one level in the tree.
        child = smallestChild(heap, pos)   // Find the next smallest child.
    return oldRoot                // Return the old root.

We use a helper function to identify the smallest child of a node. If there are no children it returns null, so that the while loop above can stop.

smallestChild(heap, pos):
    if left(pos) >= heap.size:                   // We are at a leaf.
        return null
    else if right(pos) >= heap.size:             // There is no right child.
        return left(pos)
    else if heap[left(pos)] < heap[right(pos)]:  // The left child has higher priority.
        return left(pos)
    else:                                        // The right child has higher priority.
        return right(pos)

Exercise: Delete from a min-heap

9.5.6 Changing the priority of elements

In some applications, the priority of an element may change over time, or we may need to remove an element other than the root. To support such operations efficiently, we must know the position of the element in the heap.

However, the heap invariant is not helpful for locating an arbitrary element. It guarantees only that each node has higher priority than its children. It does not tell us how elements are distributed across different subtrees. As a result, when searching for a specific element, we cannot determine which subtree to explore next. In the worst case, we must traverse the entire tree, which takes O(n) time.

Once the element has been found, updating or removing it is straightforward. To update the priority of an element, we restore the heap property by bubbling it up if its priority has increased, or down if its priority has decreased. To remove an element, we remove the last element of the array and put it in the place of the element to be removed, then we restore the heap property in the same way as when we updated the priority.

To avoid the costly O(n) search, we can maintain an auxiliary data structure that keeps track of each element’s position in the heap. For example, we can use a lookup table, or map (see Section 8.3.2), that associates each element with its index in the array. If lookup in this table takes O(\log(n)) time, then updates and removals of arbitrary elements also take O(\log(n)) time, because the remaining work consists only of restoring the heap property.