PK

PKBytes

Explore tracks
Chapter 27: Heaps and Priority Queues
27.01Intermediate / Advanced5 topics13 min4 interactive animations

Heap theory

What a binary heap is: a complete binary tree with the heap-order property, stored in an array, in its min and max forms.

Learning goals

  • Describe the two properties that define a heap: shape and order
  • Convert between a heap's tree picture and its array without pointers
  • Use the index formulas for parent, children and leaves
  • Tell min-heaps from max-heaps and from binary search trees

Prerequisites

Tree fundamentals and traversalArrays

A priority queue answers one question fast: which item is the most important right now? A binary heap answers it in O(1) and keeps itself in order in O(log n) per update, with nothing but an array.

27.01.1

Complete binary tree

A heap is a **complete binary tree**: every level is full except possibly the last, which is filled from the left. This shape is what lets a heap live in an array with no pointers, and it keeps the height as small as possible: a heap with n nodes has height ⌊log2 n⌋ (edges).

The animation shows each heap twice: as the array (index below each cell) and as the tree that the array encodes. Because the shape is fixed, there is exactly one heap shape for each n, and insertion always adds at the first free array slot and deletion removes the last one.

Nodes n12-34-78-1516-31
Height ⌊log2 n⌋01234
Java
1static int heapHeight(int n) {                   // height (in edges) of a heap with n >= 1 nodes
2    return 31 - Integer.numberOfLeadingZeros(n); // floor(log2 n)
3}

Binary heap: sift-up, sift-down, insert, extract, replace, decrease-key and build-heap

Interactive · edit the input

Your input

Try

min-heap as a tree · 8 nodes

9

[0]

7

[1]

8

[2]

3

[3]

5

[4]

2

[5]

6

[6]

1

[7]

Being comparedJust swappedSettled in placeHeap order holds

heap array (index = position in the tree)

90
71
82
33
54
25
66
17
Setup

Heapify 8 values in place: the last 4 entries are leaves, so start at the last internal node and sift each one down, moving toward the root.

Step 1 / 24
Java
1static void siftUp(int[] a, int i) {
2    while (i > 0) {
3        int p = (i - 1) / 2;                     // parent
4        if (a[p] <= a[i]) break;                 // heap order restored
5        swap(a, p, i);
6        i = p;
7    }
8}
9static void siftDown(int[] a, int n, int i) {
10    while (true) {
11        int l = 2 * i + 1, r = l + 1, m = i;
12        if (l < n && a[l] < a[m]) m = l;         // find the smallest of the node and its children
13        if (r < n && a[r] < a[m]) m = r;
14        if (m == i) break;                       // both children are larger: done
15        swap(a, i, m);
16        i = m;
17    }
18}
19static int size;
20static void insert(int[] a, int x) { a[size] = x; siftUp(a, size++); }
21static int extractMin(int[] a) {
22    int min = a[0];
23    a[0] = a[--size];                            // move the last leaf to the root
24    siftDown(a, size, 0);
25    return min;
26}
27static void buildHeap(int[] a, int n) {
28    for (int i = n / 2 - 1; i >= 0; i--) siftDown(a, n, i);   // the last n/2 entries are leaves already
29}
30static int replaceRoot(int[] a, int x) {         // pop and push in one sift
31    int min = a[0];
32    a[0] = x;
33    siftDown(a, size, 0);
34    return min;
35}
36static void decreaseKey(int[] a, int i, int x) { a[i] = x; siftUp(a, i); }

Live state

0 comparisons0 swaps

size

8

No condition evaluated on this step
Execution trace (dry run table)Show 24 steps
StepLineStateWhat happens
1L1size=8Heapify 8 values in place: the last 4 entries are leaves, so start at the last internal node and sift each one down, moving toward the root.
2L28size=8 index=3Sift down the node at index 3 (3). Everything below it is already a heap.
3L12size=8 node=3Compare 3 with its only child 1. The smaller child is 1.
4L15size=8 node=3Swap 3 with 1: the smaller value moves up.
5L12size=8 node=3Compare 3 with its children: none, it is a leaf. Neither is smaller: heap order holds here.
6L28size=8 index=2Sift down the node at index 2 (8). Everything below it is already a heap.
7L12size=8 node=8Compare 8 with its children 2 and 6. The smaller child is 2.
8L15size=8 node=8Swap 8 with 2: the smaller value moves up.
9L12size=8 node=8Compare 8 with its children: none, it is a leaf. Neither is smaller: heap order holds here.
10L28size=8 index=1Sift down the node at index 1 (7). Everything below it is already a heap.
11L12size=8 node=7Compare 7 with its children 1 and 5. The smaller child is 1.
12L15size=8 node=7Swap 7 with 1: the smaller value moves up.
13L12size=8 node=7Compare 7 with its only child 3. The smaller child is 3.
14L15size=8 node=7Swap 7 with 3: the smaller value moves up.
15L12size=8 node=7Compare 7 with its children: none, it is a leaf. Neither is smaller: heap order holds here.
16L28size=8 index=0Sift down the node at index 0 (9). Everything below it is already a heap.
17L12size=8 node=9Compare 9 with its children 1 and 2. The smaller child is 1.
18L15size=8 node=9Swap 9 with 1: the smaller value moves up.
19L12size=8 node=9Compare 9 with its children 3 and 5. The smaller child is 3.
20L15size=8 node=9Swap 9 with 3: the smaller value moves up.
21L12size=8 node=9Compare 9 with its only child 7. The smaller child is 7.
22L15size=8 node=9Swap 9 with 7: the smaller value moves up.
23L12size=8 node=9Compare 9 with its children: none, it is a leaf. Neither is smaller: heap order holds here.
24L1size=8 heap order=holds[1, 3, 2, 7, 5, 8, 6, 9]: heap order holds. 11 comparisons and 7 swaps.
27.01.2

Heap-order property

The second property is **heap order**: in a **min-heap** every node is less than or equal to its children, so the smallest key is at the root. Nothing is promised between siblings or between cousins. In the “Build bottom-up” result [1, 3, 2, 7, 5, 8, 6, 9], 3 and 2 are siblings in no particular order, and 7 is below 3 although 2 is smaller than 7.

That weak order is the reason a heap is cheap: it needs to find only the minimum, not keep everything sorted. A heap is **not** a search tree: you cannot find a given key in less than O(n) time, and an inorder traversal does not give sorted order.

Java
1static boolean isMinHeap(int[] a, int n) {
2    for (int i = 1; i < n; i++) {
3        if (a[(i - 1) / 2] > a[i]) return false;     // a parent larger than its child
4    }
5    return true;
6}

Binary heap: sift-up, sift-down, insert, extract, replace, decrease-key and build-heap

Interactive · edit the input

Your input

Try

min-heap as a tree · 8 nodes

9

[0]

7

[1]

8

[2]

3

[3]

5

[4]

2

[5]

6

[6]

1

[7]

Being comparedJust swappedSettled in placeHeap order holds

heap array (index = position in the tree)

90
71
82
33
54
25
66
17
Setup

Heapify 8 values in place: the last 4 entries are leaves, so start at the last internal node and sift each one down, moving toward the root.

Step 1 / 24
Java
1static void siftUp(int[] a, int i) {
2    while (i > 0) {
3        int p = (i - 1) / 2;                     // parent
4        if (a[p] <= a[i]) break;                 // heap order restored
5        swap(a, p, i);
6        i = p;
7    }
8}
9static void siftDown(int[] a, int n, int i) {
10    while (true) {
11        int l = 2 * i + 1, r = l + 1, m = i;
12        if (l < n && a[l] < a[m]) m = l;         // find the smallest of the node and its children
13        if (r < n && a[r] < a[m]) m = r;
14        if (m == i) break;                       // both children are larger: done
15        swap(a, i, m);
16        i = m;
17    }
18}
19static int size;
20static void insert(int[] a, int x) { a[size] = x; siftUp(a, size++); }
21static int extractMin(int[] a) {
22    int min = a[0];
23    a[0] = a[--size];                            // move the last leaf to the root
24    siftDown(a, size, 0);
25    return min;
26}
27static void buildHeap(int[] a, int n) {
28    for (int i = n / 2 - 1; i >= 0; i--) siftDown(a, n, i);   // the last n/2 entries are leaves already
29}
30static int replaceRoot(int[] a, int x) {         // pop and push in one sift
31    int min = a[0];
32    a[0] = x;
33    siftDown(a, size, 0);
34    return min;
35}
36static void decreaseKey(int[] a, int i, int x) { a[i] = x; siftUp(a, i); }

Live state

0 comparisons0 swaps

size

8

No condition evaluated on this step
Execution trace (dry run table)Show 24 steps
StepLineStateWhat happens
1L1size=8Heapify 8 values in place: the last 4 entries are leaves, so start at the last internal node and sift each one down, moving toward the root.
2L28size=8 index=3Sift down the node at index 3 (3). Everything below it is already a heap.
3L12size=8 node=3Compare 3 with its only child 1. The smaller child is 1.
4L15size=8 node=3Swap 3 with 1: the smaller value moves up.
5L12size=8 node=3Compare 3 with its children: none, it is a leaf. Neither is smaller: heap order holds here.
6L28size=8 index=2Sift down the node at index 2 (8). Everything below it is already a heap.
7L12size=8 node=8Compare 8 with its children 2 and 6. The smaller child is 2.
8L15size=8 node=8Swap 8 with 2: the smaller value moves up.
9L12size=8 node=8Compare 8 with its children: none, it is a leaf. Neither is smaller: heap order holds here.
10L28size=8 index=1Sift down the node at index 1 (7). Everything below it is already a heap.
11L12size=8 node=7Compare 7 with its children 1 and 5. The smaller child is 1.
12L15size=8 node=7Swap 7 with 1: the smaller value moves up.
13L12size=8 node=7Compare 7 with its only child 3. The smaller child is 3.
14L15size=8 node=7Swap 7 with 3: the smaller value moves up.
15L12size=8 node=7Compare 7 with its children: none, it is a leaf. Neither is smaller: heap order holds here.
16L28size=8 index=0Sift down the node at index 0 (9). Everything below it is already a heap.
17L12size=8 node=9Compare 9 with its children 1 and 2. The smaller child is 1.
18L15size=8 node=9Swap 9 with 1: the smaller value moves up.
19L12size=8 node=9Compare 9 with its children 3 and 5. The smaller child is 3.
20L15size=8 node=9Swap 9 with 3: the smaller value moves up.
21L12size=8 node=9Compare 9 with its only child 7. The smaller child is 7.
22L15size=8 node=9Swap 9 with 7: the smaller value moves up.
23L12size=8 node=9Compare 9 with its children: none, it is a leaf. Neither is smaller: heap order holds here.
24L1size=8 heap order=holds[1, 3, 2, 7, 5, 8, 6, 9]: heap order holds. 11 comparisons and 7 swaps.
27.01.3

Array index relations

With the root at index 0 and the levels stored left to right, the children of node i are at 2i + 1 and 2i + 2 and its parent is at (i - 1) / 2 (integer division). In a heap of n elements the nodes with children are exactly those at indexes below n / 2, so **the last n / 2 elements are leaves**, which is why bottom-up construction starts at index n / 2 - 1.

Many texts start at index 1, giving children 2i and 2i + 1 and parent i / 2; the formulas are shorter but waste a slot. The animation prints the index under every cell so you can check each formula by hand.

Relation0-based1-based
Left child of i2i + 12i
Right child of i2i + 22i + 1
Parent of i(i - 1) / 2i / 2
First leafn / 2n / 2 + 1
Java
1static int parent(int i) { return (i - 1) / 2; }
2static int left(int i) { return 2 * i + 1; }
3static int right(int i) { return 2 * i + 2; }
4static boolean isLeaf(int i, int n) { return left(i) >= n; }     // true exactly for i >= n / 2

Binary heap: sift-up, sift-down, insert, extract, replace, decrease-key and build-heap

Interactive · edit the input

Your input

Try

min-heap as a tree · 8 nodes

9

[0]

7

[1]

8

[2]

3

[3]

5

[4]

2

[5]

6

[6]

1

[7]

Being comparedJust swappedSettled in placeHeap order holds

heap array (index = position in the tree)

90
71
82
33
54
25
66
17
Setup

Heapify 8 values in place: the last 4 entries are leaves, so start at the last internal node and sift each one down, moving toward the root.

Step 1 / 24
Java
1static void siftUp(int[] a, int i) {
2    while (i > 0) {
3        int p = (i - 1) / 2;                     // parent
4        if (a[p] <= a[i]) break;                 // heap order restored
5        swap(a, p, i);
6        i = p;
7    }
8}
9static void siftDown(int[] a, int n, int i) {
10    while (true) {
11        int l = 2 * i + 1, r = l + 1, m = i;
12        if (l < n && a[l] < a[m]) m = l;         // find the smallest of the node and its children
13        if (r < n && a[r] < a[m]) m = r;
14        if (m == i) break;                       // both children are larger: done
15        swap(a, i, m);
16        i = m;
17    }
18}
19static int size;
20static void insert(int[] a, int x) { a[size] = x; siftUp(a, size++); }
21static int extractMin(int[] a) {
22    int min = a[0];
23    a[0] = a[--size];                            // move the last leaf to the root
24    siftDown(a, size, 0);
25    return min;
26}
27static void buildHeap(int[] a, int n) {
28    for (int i = n / 2 - 1; i >= 0; i--) siftDown(a, n, i);   // the last n/2 entries are leaves already
29}
30static int replaceRoot(int[] a, int x) {         // pop and push in one sift
31    int min = a[0];
32    a[0] = x;
33    siftDown(a, size, 0);
34    return min;
35}
36static void decreaseKey(int[] a, int i, int x) { a[i] = x; siftUp(a, i); }

Live state

0 comparisons0 swaps

size

8

No condition evaluated on this step
Execution trace (dry run table)Show 24 steps
StepLineStateWhat happens
1L1size=8Heapify 8 values in place: the last 4 entries are leaves, so start at the last internal node and sift each one down, moving toward the root.
2L28size=8 index=3Sift down the node at index 3 (3). Everything below it is already a heap.
3L12size=8 node=3Compare 3 with its only child 1. The smaller child is 1.
4L15size=8 node=3Swap 3 with 1: the smaller value moves up.
5L12size=8 node=3Compare 3 with its children: none, it is a leaf. Neither is smaller: heap order holds here.
6L28size=8 index=2Sift down the node at index 2 (8). Everything below it is already a heap.
7L12size=8 node=8Compare 8 with its children 2 and 6. The smaller child is 2.
8L15size=8 node=8Swap 8 with 2: the smaller value moves up.
9L12size=8 node=8Compare 8 with its children: none, it is a leaf. Neither is smaller: heap order holds here.
10L28size=8 index=1Sift down the node at index 1 (7). Everything below it is already a heap.
11L12size=8 node=7Compare 7 with its children 1 and 5. The smaller child is 1.
12L15size=8 node=7Swap 7 with 1: the smaller value moves up.
13L12size=8 node=7Compare 7 with its only child 3. The smaller child is 3.
14L15size=8 node=7Swap 7 with 3: the smaller value moves up.
15L12size=8 node=7Compare 7 with its children: none, it is a leaf. Neither is smaller: heap order holds here.
16L28size=8 index=0Sift down the node at index 0 (9). Everything below it is already a heap.
17L12size=8 node=9Compare 9 with its children 1 and 2. The smaller child is 1.
18L15size=8 node=9Swap 9 with 1: the smaller value moves up.
19L12size=8 node=9Compare 9 with its children 3 and 5. The smaller child is 3.
20L15size=8 node=9Swap 9 with 3: the smaller value moves up.
21L12size=8 node=9Compare 9 with its only child 7. The smaller child is 7.
22L15size=8 node=9Swap 9 with 7: the smaller value moves up.
23L12size=8 node=9Compare 9 with its children: none, it is a leaf. Neither is smaller: heap order holds here.
24L1size=8 heap order=holds[1, 3, 2, 7, 5, 8, 6, 9]: heap order holds. 11 comparisons and 7 swaps.
27.01.4

Min heap

In a **min-heap** the root is the smallest key: peek is a[0], and extractMin moves the last element to the root and sifts it down. It is the structure behind priority queues where a smaller value means higher priority: shortest distance first, earliest deadline first, smallest remaining task.

Java's PriorityQueue is a min-heap by default, as the last lesson of this chapter shows. All the animations here use the min-heap form.

Binary heap: sift-up, sift-down, insert, extract, replace, decrease-key and build-heap

Interactive · edit the input

Your input

Try

min-heap as a tree · 8 nodes

9

[0]

7

[1]

8

[2]

3

[3]

5

[4]

2

[5]

6

[6]

1

[7]

Being comparedJust swappedSettled in placeHeap order holds

heap array (index = position in the tree)

90
71
82
33
54
25
66
17
Setup

Heapify 8 values in place: the last 4 entries are leaves, so start at the last internal node and sift each one down, moving toward the root.

Step 1 / 24
Java
1static void siftUp(int[] a, int i) {
2    while (i > 0) {
3        int p = (i - 1) / 2;                     // parent
4        if (a[p] <= a[i]) break;                 // heap order restored
5        swap(a, p, i);
6        i = p;
7    }
8}
9static void siftDown(int[] a, int n, int i) {
10    while (true) {
11        int l = 2 * i + 1, r = l + 1, m = i;
12        if (l < n && a[l] < a[m]) m = l;         // find the smallest of the node and its children
13        if (r < n && a[r] < a[m]) m = r;
14        if (m == i) break;                       // both children are larger: done
15        swap(a, i, m);
16        i = m;
17    }
18}
19static int size;
20static void insert(int[] a, int x) { a[size] = x; siftUp(a, size++); }
21static int extractMin(int[] a) {
22    int min = a[0];
23    a[0] = a[--size];                            // move the last leaf to the root
24    siftDown(a, size, 0);
25    return min;
26}
27static void buildHeap(int[] a, int n) {
28    for (int i = n / 2 - 1; i >= 0; i--) siftDown(a, n, i);   // the last n/2 entries are leaves already
29}
30static int replaceRoot(int[] a, int x) {         // pop and push in one sift
31    int min = a[0];
32    a[0] = x;
33    siftDown(a, size, 0);
34    return min;
35}
36static void decreaseKey(int[] a, int i, int x) { a[i] = x; siftUp(a, i); }

Live state

0 comparisons0 swaps

size

8

No condition evaluated on this step
Execution trace (dry run table)Show 24 steps
StepLineStateWhat happens
1L1size=8Heapify 8 values in place: the last 4 entries are leaves, so start at the last internal node and sift each one down, moving toward the root.
2L28size=8 index=3Sift down the node at index 3 (3). Everything below it is already a heap.
3L12size=8 node=3Compare 3 with its only child 1. The smaller child is 1.
4L15size=8 node=3Swap 3 with 1: the smaller value moves up.
5L12size=8 node=3Compare 3 with its children: none, it is a leaf. Neither is smaller: heap order holds here.
6L28size=8 index=2Sift down the node at index 2 (8). Everything below it is already a heap.
7L12size=8 node=8Compare 8 with its children 2 and 6. The smaller child is 2.
8L15size=8 node=8Swap 8 with 2: the smaller value moves up.
9L12size=8 node=8Compare 8 with its children: none, it is a leaf. Neither is smaller: heap order holds here.
10L28size=8 index=1Sift down the node at index 1 (7). Everything below it is already a heap.
11L12size=8 node=7Compare 7 with its children 1 and 5. The smaller child is 1.
12L15size=8 node=7Swap 7 with 1: the smaller value moves up.
13L12size=8 node=7Compare 7 with its only child 3. The smaller child is 3.
14L15size=8 node=7Swap 7 with 3: the smaller value moves up.
15L12size=8 node=7Compare 7 with its children: none, it is a leaf. Neither is smaller: heap order holds here.
16L28size=8 index=0Sift down the node at index 0 (9). Everything below it is already a heap.
17L12size=8 node=9Compare 9 with its children 1 and 2. The smaller child is 1.
18L15size=8 node=9Swap 9 with 1: the smaller value moves up.
19L12size=8 node=9Compare 9 with its children 3 and 5. The smaller child is 3.
20L15size=8 node=9Swap 9 with 3: the smaller value moves up.
21L12size=8 node=9Compare 9 with its only child 7. The smaller child is 7.
22L15size=8 node=9Swap 9 with 7: the smaller value moves up.
23L12size=8 node=9Compare 9 with its children: none, it is a leaf. Neither is smaller: heap order holds here.
24L1size=8 heap order=holds[1, 3, 2, 7, 5, 8, 6, 9]: heap order holds. 11 comparisons and 7 swaps.
27.01.5

Max heap

A **max-heap** flips every comparison: each node is at least as large as its children, and the largest key is at the root. It is what heap sort uses, and what you want for 'the biggest item first'. Rather than writing a second version, either reverse the comparator (Collections.reverseOrder()) or store negated keys in a min-heap.

The two differ by one comparison sign, so every min-heap routine becomes a max-heap routine by swapping < and >. The code shows the sift-down of a max-heap.

Java
1static void siftDownMax(int[] a, int n, int i) {
2    while (true) {
3        int l = 2 * i + 1, r = l + 1, m = i;
4        if (l < n && a[l] > a[m]) m = l;         // the largest of the node and its children
5        if (r < n && a[r] > a[m]) m = r;
6        if (m == i) return;
7        swap(a, i, m);
8        i = m;
9    }
10}

Practice ladder

Now try it yourself

Easy

  • Last Stone Weight
  • Kth Largest Element in a Stream

Medium

  • Kth Largest Element in an Array
  • Top K Frequent Elements

Advanced

  • Find Median from Data Stream
  • Merge k Sorted Lists

Key takeaways

  • A heap is a complete binary tree with heap order: every parent is at most (min-heap) or at least (max-heap) its children.
  • It lives in an array: children of i at 2i + 1 and 2i + 2, parent at (i - 1) / 2, leaves from n / 2.
  • Its height is ⌊log2 n⌋, which makes every update O(log n).
  • A heap gives the extreme in O(1) but is not sorted and cannot search quickly.