← ⛰️ Heaps & Priority Queues
Subtopic 2 of 3

3.2Building a heap: bottom-up in O(n)

The idea

Building a heap bottom-up (Floyd) sifts down every non-leaf node and costs only O(n); inserting one by one costs O(n log n) in the worst case.

Think of it like this: Fixing a company from the bottom: small teams sort themselves out first, so few people have to travel far.

Why it exists

The O(n) bound is a famous non-obvious result, and GATE asks the resulting array after a build.

How it works

  1. Start at the last non-leaf index ⌊n/2⌋ − 1.
  2. Sift that node down, swapping with the larger child while needed.
  3. Move to the previous index until you reach the root.
  4. Most nodes are near the leaves and move at most a level or two, so the sum is linear.

Worked example: Build from 4 1 3 2 16 9 10 14 8 7

Floyd gives 16 14 10 8 7 9 3 2 4 1 with 7 swaps; repeated insertion gives 16 14 10 8 7 3 9 1 4 2, a different valid heap.

Now play with it

  • →Run the Floyd method, then switch to insertion and compare the final arrays.
  • →Use "Extract max" a few times and watch the root being replaced.
40113223164951061478879
index: 0 1 2 3 4 5 6 7 8 9 value: 4 1 3 2 16 9 10 14 8 7
Swaps so far0
Final swaps7
Parent of i⌊(i − 1) / 2⌋
Children of i2i + 1, 2i + 2
  • Start: 4 1 3 2 16 9 10 14 8 7
  • heapify index 4
  • heapify index 3
  • swap 2 down, 14 up
  • heapify index 2
  • swap 3 down, 10 up
  • heapify index 1
  • swap 1 down, 16 up
  • swap 1 down, 7 up
  • heapify index 0
  • swap 4 down, 16 up
  • swap 4 down, 14 up
  • swap 4 down, 8 up
  • max-heap: 16 14 10 8 7 9 3 2 4 1
removed so far: 0

Check yourself

Building a max-heap from n unsorted numbers using the bottom-up method takes

Remember: Floyd build = O(n); insertion build = O(n log n); the two can differ.
Exam notes (the dense version)

Heapify (sift down) every non-leaf from index ⌊n/2⌋ − 1 down to 0. Most nodes are near the bottom and move only a little, so the total work is O(n), not O(n log n). Building by repeated insertion (sift up) costs O(n log n) in the worst case, and the two methods can produce different heaps.

Previous year questions: Heaps & Priority Queues (9)

PYQs are grouped by topic, so this is the full set for Heaps & Priority Queues; try the ones that match this subtopic. Open all 9 on the topic page.