PK

PKBytes

Explore tracks
Chapter 27: Heaps and Priority Queues
27.02Intermediate / Advanced7 topics18 min6 interactive animations

Heap operations

The heap operations: sift-up, sift-down, insert, peek, extract, replace the root and building a heap in O(n).

Learning goals

  • Restore heap order with sift-up and sift-down
  • Implement insert, peek and extract on an array
  • Use replace-root and decrease-key where they save work
  • Build a heap bottom-up in O(n) and explain why it beats repeated insertion

Prerequisites

Heap theory

Every heap operation is the same repair: put an element in the wrong place and let it slide along one root-to-leaf path until order is restored.

27.02.1

Sift up

**Sift-up** (also called bubble-up or percolate-up) moves a node toward the root while it is smaller than its parent: compare with the parent, swap if smaller, and continue from the parent's position. Each step moves one level, so the cost is at most the height, O(log n), and often much less. In the “Insert 2 (sift-up)” preset the new value 2 swaps twice, taking 3 comparisons.

Heap order below the moving node is never disturbed: the displaced parent is no larger than the old subtree, because it was above it already.

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}

Best

O(1)

Average

O(1)

Worst

O(log n)

Space

O(1)

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.02.2

Sift down

**Sift-down** moves a node toward the leaves while a child is smaller: find the smaller of the (up to two) children, swap if it is smaller than the node, and continue from there. It needs up to two comparisons per level, so up to 2 log2 n in the worst case. Choose the **smaller** child, or the other child would end up above a smaller sibling.

In the “Extract the minimum (sift-down)” preset the last leaf 6 moves to the root of [1, 3, 5, 7, 9, 8, 6] and sinks one level, using 4 comparisons in all, ending in [3, 6, 5, 7, 9, 8].

Java
1static void siftDown(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;         // find the smallest of the node and its children
5        if (r < n && a[r] < a[m]) m = r;
6        if (m == i) break;                       // both children are larger: done
7        swap(a, i, m);
8        i = m;
9    }
10}

Best

O(1)

Average

O(log n)

Worst

O(log n)

Space

O(1)

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.02.3

Insert

To insert, place the new value in the first free slot (index size), which keeps the shape complete, and sift it up. The cost is O(log n) worst case, but on average only O(1) swaps for random data, because most elements belong near the bottom. In the animation's “Build by insertion” presets you can compare the effect on sorted and reverse-sorted input.

When the array is full, grow it by doubling, as for any dynamic array; that is the amortised O(1) cost of the array on top of the heap's own O(log n).

Java
1static int size;
2static void insert(int[] a, int x) {
3    a[size] = x;                                 // the first free slot keeps the tree complete
4    siftUp(a, size++);
5}
6static void siftUp(int[] a, int i) {
7    while (i > 0 && a[(i - 1) / 2] > a[i]) { swap(a, (i - 1) / 2, i); i = (i - 1) / 2; }
8}

Best

O(1)

Average

O(1)

Worst

O(log n)

Space

O(1)

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.02.4

Peek

peek returns the root, a[0], without changing anything: O(1). This is the whole point of the structure. Guard the empty case (return null or throw), since the array may hold stale values past size.

Java
1static int size;
2static int peek(int[] a) {
3    if (size == 0) throw new NoSuchElementException("empty heap");
4    return a[0];
5}

Best

O(1)

Average

O(1)

Worst

O(1)

Space

O(1)

27.02.5

Extract-min/max

To extract the minimum, remember the root, move the **last** element to the root (this keeps the shape complete), shrink the size, and sift the new root down. The cost is O(log n). It is the only operation that needs sift-down on a single element, and extracting everything gives sorted order, which is heap sort.

The “Extract the minimum (sift-down)” preset shows [1, 3, 5, 7, 9, 8, 6] becoming [3, 6, 5, 7, 9, 8]; the heap shrank by one and the root changed from 1 to 3.

Java
1static int size;
2static int extractMin(int[] a) {
3    int min = a[0];
4    a[0] = a[--size];                            // move the last leaf to the root
5    siftDown(a, size, 0);
6    return min;
7}
8static void siftDown(int[] a, int n, int i) {
9    while (true) {
10        int l = 2 * i + 1, r = l + 1, m = i;
11        if (l < n && a[l] < a[m]) m = l;
12        if (r < n && a[r] < a[m]) m = r;
13        if (m == i) return;
14        swap(a, i, m);
15        i = m;
16    }
17}

Best

O(1)

Average

O(log n)

Worst

O(log n)

Space

O(1)

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.02.6

Replace root

**Replace root** pops the minimum and pushes a new value in a single sift-down: put the new value at the root and sink it. It does one pass of O(log n) where poll followed by add would do a sift-down and a sift-up. It is the right tool for keeping the k largest values (replace the smallest if the newcomer is larger) and for k-way merging (replace the popped head with the next element of its list).

The “Replace the root” preset replaces 1 with 4 in [1, 3, 5, 7, 9, 8, 6] and gets [3, 4, 5, 7, 9, 8, 6] after 4 comparisons and 1 swap.

Java
1static int size;
2static int replaceRoot(int[] a, int x) {         // returns the old minimum
3    int min = a[0];
4    a[0] = x;
5    siftDown(a, size, 0);                        // one sift instead of an extract plus an insert
6    return min;
7}
8static void siftDown(int[] a, int n, int i) {
9    while (true) {
10        int l = 2 * i + 1, r = l + 1, m = i;
11        if (l < n && a[l] < a[m]) m = l;
12        if (r < n && a[r] < a[m]) m = r;
13        if (m == i) return;
14        swap(a, i, m);
15        i = m;
16    }
17}

Best

O(1)

Average

O(log n)

Worst

O(log n)

Space

O(1)

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.02.7

Build-heap in O(n)

Turning an arbitrary array into a heap by n insertions costs O(n log n). **Floyd's bottom-up construction** does better: the last n / 2 elements are already one-element heaps, so go from the last internal node down to the root and sift each one down. Most nodes are near the bottom, where sift-down is cheap: about n / 2 nodes sift down 0 levels, n / 4 sink at most 1, n / 8 at most 2 and so on, so the total work is bounded by n · (1/2 + 2/4 + 3/8 + ...) = 2n. Bottom-up construction uses at most about 2n comparisons.

On the array [9, 7, 8, 3, 5, 2, 6, 1] the “Build bottom-up” preset uses 11 comparisons and 7 swaps, while the “Build by insertion” preset needs 12 comparisons and 9 swaps. The gap grows on reverse-ordered input: for [8, 7, 6, 5, 4, 3, 2, 1] insertion needs 13 comparisons and 13 swaps against bottom-up's 10 comparisons.

Java
1static void buildHeap(int[] a, int n) {
2    for (int i = n / 2 - 1; i >= 0; i--) siftDown(a, n, i);   // the last n / 2 entries are leaves already
3}
4static void siftDown(int[] a, int n, int i) {
5    while (true) {
6        int l = 2 * i + 1, r = l + 1, m = i;
7        if (l < n && a[l] < a[m]) m = l;
8        if (r < n && a[r] < a[m]) m = r;
9        if (m == i) return;
10        swap(a, i, m);
11        i = m;
12    }
13}

Best

O(n)

Average

O(n)

Worst

O(n)

Space

O(1)

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.

Practice ladder

Now try it yourself

Easy

  • Last Stone Weight
  • Relative Ranks

Medium

  • Kth Largest Element in an Array
  • Sort an Array (heap sort)

Advanced

  • Minimum Number of Refueling Stops
  • Maximum Performance of a Team

Key takeaways

  • Sift-up moves a node toward the root, sift-down toward the leaves along the smaller child; both cost O(log n).
  • Insert adds at the first free slot and sifts up; extract moves the last leaf to the root and sifts down.
  • Replace-root does one sift where poll plus add would do two.
  • Bottom-up build-heap costs O(n), at most about 2n comparisons, against O(n log n) for repeated insertion.