Binary Heap: A Priority Queue in an Array

Fifteen keys sit in an array, and the array is also a tree: the two keys under position i are at 2i + 1 and 2i + 2. Build them into a heap one at a time or from the last parent, step through every comparison and swap, then take out the smallest and watch the next one rise.

Worked example — Binary Heap: A Priority Queue in an Array

Keys	15
Built one at a time	34 comparisons, 34 swaps
Most comparisons one at a time can need	34
Built from the last parent	22 comparisons, 11 swaps
Most comparisons from the last parent can need	22
Orders of 15 different keys that are heaps	21,964,800 of 1,307,674,368,000

These are the values the calculator shows when the page opens. Change any input above to recompute them.

Loading interactive simulation...

Lesson

The theory — Binary Heap: A Priority Queue in an Array

A binary min-heap is an array in which the key at each position i is no larger than the keys at positions 2i + 1 and 2i + 2, its children; the parent of position i is ⌊(i − 1) / 2⌋. Read that way, the array is a complete binary tree, and the smallest key is always at position 0, the root. To insert, put the key at the end and sift it up, swapping it with its parent while it is the smaller. To take out the smallest, move the last key to the root and sift it down, swapping it with its smaller child while that child is smaller. A heap used this way is a priority queue.

What each symbol means

n: the number of keys in the heap
i: a position in the array, counted from 0
h: the height of a position: how many levels lie below it, ⌊log₂(n / (i + 1))⌋

Assumes: A comparison is one key tested against another, and a swap exchanges two positions; moving the last key to the root during an extract is neither. A key equal to its parent, or to its smaller child, stays where it is, and between two equal children the left one is taken. The heap keeps the smallest key on top; a max-heap is the same with every comparison reversed. Up to fifteen keys from 0 to 99, so the whole tree fits on a phone. The orders counted in the last row are of different keys.

One at a time pays for depth, from the last parent pays for height 🖖

Press Largest first, one at a time. Every new key is smaller than everything already in the heap, so it climbs from the bottom to the root, one comparison and one swap per level: 0 for the root, 1 each for the next two, 2 each for the next four, 3 each for the last eight. That is 34. Now press Largest first, from the last parent. The same fifteen keys are laid down as they came, and each position that has children is sunk, from 6 back to 0. A key can sink only as far as there are levels below it, and eight of the fifteen positions are leaves with nothing below: the very positions the first method paid three levels each for cost nothing here. The heights add up to 11, at two comparisons a level: 22. In any heap the heights add up to n minus the number of 1s in n written in binary, so this build never needs 2n comparisons. At 1,023 keys arriving largest first the two methods need 8,194 and 2,026.

Smallest first, the two builds cost the same 14 comparisons 🖖

Press Smallest first, one at a time. Each new key is already no smaller than its parent: one comparison, no swap, 14 in all. Switch to From the last parent and it is 14 again, because each parent compares its two children and then the smaller one with itself, and stops. Fourteen is the floor for both: every key but the root has to be compared at least once. The two methods part on the way up from there, and largest first drives one at a time all the way to its ceiling. Shuffled keys land much nearer the floor. Over 200 shuffles of 1,000 keys, one at a time averaged 2,235 comparisons and the bottom-up build 1,862, against 7,987 when the same keys arrive largest first. At fifteen keys the margin is thin: press Shuffle a few times and one at a time will now and then win.

A heap is a long way from sorted 🖖

A heap promises one thing: no key is larger than the two below it. Of the 5,040 orders of seven different keys, 80 keep that promise. The smallest must be at the root, any three of the other six may form the left subtree, and each subtree must itself be a heap, which is 7! divided by the size of every subtree, 7 · 3 · 3. For fifteen keys the results table gives 21,964,800 heaps among 1,307,674,368,000 orders, and only one of them is sorted. That slack is why a heap is cheap to build. The order comes out one key at a time: press Heapsort. Each time the root is taken, the last key moves up to fill the gap and sinks, and the next smallest rises. Twelve keys come out 3, 7, 12 and on up to 93.

Problem solved in full

How many comparisons does each build cost at a thousand keys? 4 steps
Press Largest first, one at a time and then Largest first, from the last parent, and explain the 34 and the 22. Then take 1,023 keys arriving largest first. How many comparisons does each method make?

Open this problem in the tool
1. Position i sits at depth ⌊log₂(i + 1)⌋: one position at depth 0, two at 1, four at 2, eight at 3. Arriving largest first, each new key is the smallest so far and climbs to the root, one comparison and one swap per level: 0 + 2 · 1 + 4 · 2 + 8 · 3 = 34.
  
  $0 + 2 \cdot 1 + 4 \cdot 2 + 8 \cdot 3 = 34$
2. From the last parent, what counts is height: 3 for the root, 2 for positions 1 and 2, 1 for the four at depth 2, 0 for the eight leaves, 11 in all. Largest first, every key sinks the whole way, and with fifteen keys every parent has two children, so each level costs two comparisons: 22 comparisons, 11 swaps.
  
  $3 + 2 \cdot 2 + 4 \cdot 1 = 11, 2 \times 11 = 22$
3. 1,023 = 2¹⁰ − 1 is a full tree of ten levels, with 2ᵈ positions at depth d. One at a time costs the sum of the depths: 1 · 2 + 2 · 4 + 3 · 8 + ⋯ + 9 · 512 = 8,194 comparisons, and as many swaps.
  
  $d = 0 \sum 9 d \cdot 2^{d} = 8 \cdot 2^{10} + 2 = 8194$
4. From the last parent costs twice the sum of the heights. There are 2⁹ positions of height 0, 2⁸ of height 1, and so on up to the root at height 9: 1 · 256 + 2 · 128 + ⋯ + 9 · 1 = 1,013, which is 1,023 minus the ten 1s in its binary form. Twice that is 2,026 comparisons, with 1,013 swaps.
  
  $h = 0 \sum 9 h \cdot 2^{9 - h} = 1023 - 10 = 1013, 2 \times 1013 = 2026$
Answer

8,194 comparisons one at a time, 2,026 from the last parent, about eight per key against two. Most of a heap's positions are deep and short: insertion pays for the depth, the build from the last parent pays for the height. The tool stops at fifteen keys, where the same arithmetic gives the 34 and 22 it prints.

$8194 against 2026$

Learning path

What a data structure makes cheap

References (2)

Heapsort as first published: J. W. J. Williams, "Algorithm 232: Heapsort," Communications of the ACM 7(6), 347–348, June 1964.
The heap-based sort published six months later, close to the version used today: Robert W. Floyd, "Algorithm 245: Treesort 3," Communications of the ACM 7(12), 701, December 1964.

By the 42Math team · Reviewed against published sources. Corrections welcome.