Skip to content

Heaps

A binary heap is a complete binary tree that satisfies the heap property: the key of each node is either greater than or less than its children, depending on the type of heap. A binary heap is an efficient implementation of the priority queue abstract data type.

Operation Average Worst
Access1 $\htmlClass{text-green}{\Theta(1)}$ $\htmlClass{text-green}{\mathcal{O}(1)}$
Insert $\htmlClass{text-green}{\Theta(\log(n))}$ $\htmlClass{text-green}{\mathcal{O}(\log(n))}$
Delete2 $\htmlClass{text-green}{\Theta(\log(n))}$ $\htmlClass{text-green}{\mathcal{O}(\log(n))}$

In a max heap, the key of each node is greater than its children. In a min heap, the key of each node is less than its children. Siblings may be sorted in any left-to-right order.

The complete nature of a binary heap allows it to be compactly stored in an array .

Storing a complete binary tree as an array, with nodes indexed by level (top-to-bottom), and siblings indexed left-to-right

(original)

When storing a binary tree in an array, given a node at index $i$, the location of a node’s parent and children can be computed as:

Node Parent Left child Right child
$i$ $\lfloor \dfrac{i - 1}{2} \rfloor$ $2i + 1$ $2i + 2$

Up-heap bubbling

A key can be inserted at the end of the tree, then “bubbled” up to its correct placement by comparing the key to its parent:

  1. Compare the key to its parent
    • If the parent is > the key (or < the key in a max heap), swap the key and parent
      • Repeat the comparison with the new parent
    • Otherwise, the heap property is satisfied for the tree and the insertion is successful

Inserting a key in a min heap via up-heap bubbling

(original)

Down-heap bubbling

In a priority queue, the first ordered key is the only one that is eligible for removal. To remove it, replace it with the last key in the tree. Then compare the new root key with its children, “bubbling” it down to its correct placement:

  1. Compare the root key with its smallest child (largest in a max heap).
    • If the smallest child is < the key (or the largest child > the key in a max heap), swap the key and child
      • Repeat the comparison with the new children
    • Otherwise, the heap property is satisfied for the tree and the deletion is successful

Removing the min key in a min heap via down-heap bubbling

(original)

Implementation

This example implements a min heap using a dynamic array to store the heap tree data:

 1public class BinaryMinHeapPriorityQueue<P extends Comparable<P>,V> implements PriorityQueueADT<P, V> {
 2    private class Node {
 3        P key;
 4        V value;
 5
 6        public Node(P key, V value) {
 7            this.key = key;
 8            this.value = value;
 9        }
10    }
11
12    private final DynamicArrayList<Node> heap = new DynamicArrayList<>();
13
14    public int size() { return heap.size(); };
15
16    public boolean isEmpty() { return heap.isEmpty(); }
17
18    public V peek() {
19        if (isEmpty()) return null;
20        return heap.get(0).value;
21    }
22
23    public void enqueue(P key, V value) {
24        var newNode = new Node(key, value);
25        heap.add(heap.size(), newNode);
26        upHeapBubble(heap.size() - 1);
27    }
28
29    public V dequeue() {
30        if (isEmpty()) return null;
31        var result = heap.get(0).value;
32        swap(0, heap.size() - 1); // swap the min and last items
33        heap.remove(heap.size() - 1); // remove the min item
34        downHeapBubble(0);
35        return result;
36    }
37
38    private void upHeapBubble(int index) {
39        while (index > 0) {
40            int parent = parent(index);
41            // if the child is >= the parent, the heap property is satisfied
42            if (compare(index, parent) >= 0)
43                return;
44            // otherwise, swap the parent and child
45            swap(index, parent);
46            index = parent;
47        }
48    }
49
50    private void downHeapBubble(int index) {
51        int left = left(index);
52        while (left < heap.size()) {
53            // find the smallest child
54            int smallest = left(index);
55            int right = right(index);
56            if (right < heap.size() && compare(smallest, right) > 0)
57                smallest = right;
58            // if the smallest child is > than the node, heap property is satisfied
59            if (compare(smallest, index) >= 0)
60                return;
61            // otherwise, swap the node with its smallest child
62            swap(index, smallest);
63            index = smallest;
64            left = left(index);
65        }
66    }
67
68    private int parent(int j) { return (j - 1) / 2; }
69
70    private int left(int j) { return (2 * j) + 1; }
71
72    private int right(int j) { return left(j) + 1; }
73
74    private int compare(int index, int index2) {
75        P key = heap.get(index).key;
76        P key2 = heap.get(index2).key;
77        return key.compareTo(key2);
78    }
79
80    private void swap(int i, int j) {
81        var temp = heap.get(i);
82        heap.set(i, heap.get(j));
83        heap.set(j, temp);
84    }
85}

  1. Specifically, “peeking” the minimum value (in a min heap) or the maximum value (in a max heap). ↩︎

  2. Specifically, removing the minimum value (in a min heap) or the maximum value (in a max heap). ↩︎