Faangprep Logo
Log inStart free
Browse curriculum

Sorting with a Binary Heap

Heap sort with a binary heap sorts an array in place by repeatedly extracting the maximum, with sift-down doing every bit of the work.

BUILD HEAP

Array — the heap and the sorted tail share it

12

0

11

1

13

2

5

3

6

4

7

5

 

Initial Array

Next

Build Heap: Compare node 13 with children

Array

Intuition

A heap promises one thing: the largest element is at the root, and you can read it in O(1). Sorting follows from that promise without a new idea. Take the root, put it where it belongs, shrink the heap by one, and restore the property.

So heap sort is not really a sorting algorithm you have to learn. It is N-1 extractions of the structure you already built in the previous lesson, arranged so that the extracted values land in the space the heap is vacating — which is why it needs no second array.

Concept

One array, two regions:

  • Build: sift down from the last internal node, index n/2 - 1, backwards to the root. This is O(N), not O(N log N) — half the nodes are leaves and sift no distance at all, and the cost is dominated by the many cheap nodes rather than the few expensive ones.
  • Extract: swap the root with the last live element, shrink the heap by one, then sift the new root down. The element swapped out is in its final position and is never touched again.
  • The boundary: the heap occupies a prefix of the array and the sorted tail occupies the suffix. Every extraction moves the boundary one step left. When the heap holds one element the whole array is sorted.

Sift-down is the only operation in the algorithm. Build calls it N/2 times, extract calls it N-1 times, and nothing else moves an element.

How it Works

The figure draws the array as the binary tree its indices imply, so sift-down is a visible walk down a path rather than an arithmetic step.

  1. The build pass runs first. Watch how shallow most of it is: the nodes near the leaves settle in one comparison.
  2. Once the heap is built, the root is the maximum. It trades places with the last live element.
  3. The swapped-out value leaves the tree and joins the sorted tail, which grows leftwards as the tree shrinks.
  4. The new root is almost certainly in the wrong place, so it sifts down until the property holds again — at most log N levels.

Step-by-Step Breakdown

The six stages the figure steps through, each lighting the line of code that produced it:

  1. Compare a node against the better of its children.
  2. The comparison lost, so the two trade places and the walk continues downwards.
  3. The build pass is finished and the whole array satisfies the heap property.
  4. The root swaps with the last element still inside the heap.
  5. That element is now final; the heap is one smaller.
  6. One element left in the heap, so the array is sorted.

When to Use

  • You need a guaranteed O(N log N) with no worst case to fear — unlike quicksort, no input degrades it.
  • You cannot spare O(N) scratch memory, which rules out merge sort.
  • You are already maintaining a heap, so the build phase is free.
  • You need the k largest elements rather than a full sort: stop after k extractions and pay O(N + k log N).

When NOT to Use

  • Stability matters. Swapping the root with a distant leaf reorders equal elements.
  • Raw average speed matters. Parent and child indices are far apart in memory, so nearly every sift-down misses the cache; a well-implemented quicksort usually wins in practice despite the worse bound.
  • The data is nearly sorted. Heap sort is not adaptive and pays full price anyway, where insertion sort would finish in close to O(N).

How to Identify

"Sort in place with guaranteed O(n log n)", "no extra memory", "k largest elements", "repeatedly remove the maximum".

Applying for software engineering roles? Free, no sign-up:

AI resume checker — match your resume to the job description
Previous

Heap Operations

Next

Introduction

Frequently Asked Questions

Why is building the heap O(N) and not O(N log N)?

Because the cost is dominated by the cheap nodes. Half the array is leaves and sifts no distance, a quarter sifts at most one level, and only the root can sift log N. Summing height times node count over the levels converges to O(N).

Where does the sorted output go if there is no second array?

Into the space the heap gives up. Each extraction swaps the root with the last element still inside the heap and then shrinks the heap by one, so the element that leaves lands exactly where the heap no longer reaches. The array holds the heap as a prefix and the sorted values as a suffix.

Why is heap sort often slower than quicksort in practice?

Locality. A parent at index i has children at 2i+1 and 2i+2, so sift-down jumps further through memory at every level and misses the cache almost every time, while quicksort scans contiguous runs. Heap sort still wins where the O(N²) worst case is unacceptable or O(N) scratch memory is unavailable.

Is heap sort stable?

No. The root is swapped with a distant leaf rather than a neighbour, so two equal values can be reordered. Sorting records by a key that must keep its original order needs merge sort, or a tie-breaker added to the comparison.