A max heap is a complete binary tree where every parent is greater than or equal to its children, so the largest value is always at the root. A min heap is the same rule inverted, so the smallest value is at the root.

What does heapify mean?

Heapify is the process that restores the heap property. Sift-down pushes a node down until it is larger than both children (max heap), and sift-up pulls a node up past smaller parents. Building a heap of n items costs O(n).

How does the heap relate to Heap Sort?

Heap Sort builds a max heap, then repeatedly swaps the root (the maximum) with the last element and sifts down the smaller root, giving an in-place O(n log n) sort. The unlocked Heap Sort visualizer shows the same tree driving a sorted array.

Why are heaps used for priority queues?

A heap supports peeking the maximum or minimum in O(1), and extracting it or inserting a new item in O(log n). That makes the binary heap the standard data structure behind priority queues and schedulers.

Interactive tool

Heap Visualizer

Build max heaps and min heaps on a live binary tree. Watch heapify restore order from the leaves to the root, insertions bubble up, and extractions sift down, exactly the motions that power Heap Sort.

Live heap tree

Max heap

Orange nodes were just compared or swapped. Green nodes hold their final heap position.

Underlying array (0-indexed). Children of index i sit at 2i+1 and 2i+2.

Step log

Every swap written out while the heap builds, inserts, and extracts.

Click Build heap to begin, or shuffle to load random data.

01What you are watching

The heap rule

Every parent must dominate its children. In a max heap the root is the largest value; in a min heap it is the smallest. Violations are fixed by swapping along the tree.

Heapify builds order from the bottom

Building starts at the last parent and walks up. Each parent sifts down until its whole subtree obeys the rule, so by the time the root is processed the entire tree is a valid heap.

Insertion bubbles up

A new value is appended as a leaf, then it trades places with parents until the heap rule holds again, costing at most tree height, O(log n).

Extraction sifts down

The root leaves, the last leaf takes its place, and the smaller (or larger) child is picked each round until order returns. This is the exact loop hidden inside Heap Sort.

02From heap to Heap Sort

A heap is not only a useful priority queue, it is also a sorting machine. Heap Sort builds a max heap, then repeats two moves: swap the root with the last element, shrink the array by one, and sift the new root down. The result is an in-place sort with a worst case of O(n log n) and no extra memory.

Once the building and sifting motions make sense here, open the Heap Sort visualizer to see the same tree powering a completely sorted array, then compare it against other sorts in the Algorithm Race.

Open Heap Sort visualizer Race all eight sorts

03Frequently asked questions

QIs a heap the same as a sorted tree?

No. A heap only guarantees the parent-child rule, so the array is not fully sorted. This weaker guarantee is exactly why building a heap costs O(n) while fully sorting costs O(n log n).

QWhy is building a heap O(n) and not O(n log n)?

Most nodes are near the bottom and sift down only a few levels. The sum of heights over all nodes is O(n), not O(n log n). Bottom-up heapify finishes in linear time even though inserting n items one by one would be O(n log n).

QWhere are heaps used in the real world?

Priority queues, OS schedulers, Dijkstra's shortest path, streaming top-k queries, and the internal workhorse of Heap Sort. Any place that repeatedly needs the current maximum or minimum while handling a steady stream of inserts.