Sorting Algorithm

Heap Sort

Arranges the array into a max-heap — a binary tree where every parent is bigger than its children — then repeatedly swaps the root (the maximum) to the end and shrinks the heap. It's in-place like quicksort, but with a guaranteed O(n log n) worst case, which is why it's chosen when predictability matters more than raw average speed.

BestO(n log n)
AverageO(n log n)
WorstO(n log n)
SpaceO(1)
StableNo

Try It — Animated Flow

29
8
44
15
3
37
21
Heap sort first arranges the array into a max-heap, then repeatedly moves the largest value to the end.
Step 1 / 42
Pointer / current
Comparing
Swapping / removing
Newly inserted
Settled

Java Implementation

Real-Life Usage

The Linux kernel's sort()
Linux's generic in-kernel sort function uses heap sort specifically because it needs O(1) space and no recursion — quicksort's stack depth is a real risk in kernel space.
Real-time / safety-critical systems
Where a hard worst-case time bound is a requirement (e.g. avionics, industrial control), heap sort's guaranteed O(n log n) beats quicksort's O(n²) worst case.
Priority queues & schedulers
The binary heap heap sort is built on is the exact structure behind priority queues — task schedulers and Dijkstra's shortest-path algorithm both rely on it.
Finding the top-K elements
Maintaining a heap of size K while scanning a huge stream is the standard way to track the K largest/smallest values without sorting everything.

Trade-offs

Reach for it when
  • A guaranteed worst-case O(n log n) is required
  • You need O(1) extra space with no recursion
  • You're implementing a priority queue or top-K selection
Avoid it when
  • Stability is required (heap sort can reorder equal elements)
  • Average-case raw speed matters more than worst-case guarantees (quicksort usually wins in practice)
  • You're sorting a linked list (heaps need array-style indexing)