vizlearn
Home / Algorithms

Heaps and Priority Queues

Algorithms & Data StructuresBy Updated

A tree that only promises one thing: the smallest item is at the top. That weaker guarantee is what makes insert and extract cost O(log n) — and it is the engine inside Dijkstra and A*.

Controls

Tree and Array Are the Same Thing

step 0
Backing array — no pointers needed

Insight

A heap is a complete binary tree where every parent beats its children. Siblings are unordered — that is the weakness which buys the speed.

parent(i) = (i-1)/2 left(i) = 2i + 1 right(i) = 2i + 2
size0
height0
root–
last swaps–

Complexity

Peek min/max O(1)
Insert / extract O(log n)
Build heap O(n)

Overview

A heap is a complete binary tree obeying one rule: every parent is smaller than both its children (a min-heap) or larger than both (a max-heap). It says nothing about siblings — the tree is only partially ordered.

The problem it solves

That partial ordering is what makes a heap useful. It guarantees the smallest (or largest) element is always at the root, and it can be maintained in O(log n) per insertion or removal.

Why Partial Ordering Is Better Here

A BST fully sorts its data, which costs effort to maintain. A heap only guarantees the extreme value sits at the root. If all you ever ask is "what is the smallest item?", full sorting is wasted work.

That weaker promise makes the structure cheap to maintain: O(1) to read the root, O(log n) to insert or remove it. Note that heaps are terrible at searching for an arbitrary value — that is O(n), because the ordering gives you no guidance below the root.

An Array Pretending to Be a Tree

Heaps need no pointers at all. Because the tree is complete — every level full except possibly the last, filled left to right — positions can be computed with arithmetic:

Watch the tree and the array update together as you insert. They are the same structure drawn two ways. This makes heaps compact and cache-friendly — a real advantage over pointer-based trees.

Sift Up and Sift Down

  • Insert — place the new value at the end of the array (the only spot that keeps the tree complete), then sift up: repeatedly swap with the parent while it is out of order. At most one swap per level, so O(log n).
  • Extract root — take the root, move the last element into its place, then sift down: repeatedly swap with the smaller child until order is restored. Again O(log n).

The swap counter shows this: even with 15 elements, no operation needs more than about 4 swaps.

Try it yourself: Heaps and Priority Queues

  1. Insert a value smaller than the root. Watch it bubble all the way to the top — one swap per level, never more.
  2. Insert a large value. It stays near the bottom with no swaps at all — the average insert is far cheaper than the worst case.

The limitation: no efficient search or update

A heap answers "what is the smallest?" and nothing else. Finding an arbitrary element requires scanning — O(n) — because siblings are unordered.

That matters for algorithms that want to decrease a key: Dijkstra ideally updates a node's priority in place, and a binary heap cannot locate that node quickly. The standard workaround is lazy deletion — push a new entry and skip stale ones when popped — which is why Dijkstra implementations carry that check.

If you need both priority access and lookup, the usual answer is a heap plus a dictionary from item to its position, maintained together. That is more code and it is what a proper indexed priority queue provides.

NeedStructure
Smallest or largest, repeatedlyHeap
Sorted iterationSorted list, or a balanced tree
Lookup by keyHash table
Range queriesBalanced tree
Priority plus lookupHeap plus an index dictionary

A worked heap trace

Building a max-heap from [3, 9, 2, 1, 4, 5] by sifting down from the middle backwards makes the O(n) build concrete.

Indices 5, 4, 3 are leaves and need nothing. Start at index 2:

StepNodeChildrenActionArray
Start———[3, 9, 2, 1, 4, 5]
i = 225 (index 5)Swap[3, 9, 5, 1, 4, 2]
i = 191, 4Already largest[3, 9, 5, 1, 4, 2]
i = 039, 5Swap with 9[9, 3, 5, 1, 4, 2]
i = 0 cont.31, 4Swap with 4[9, 4, 5, 1, 3, 2]

Final heap: [9, 4, 5, 1, 3, 2]. The root is the maximum, every parent exceeds its children, and the siblings are unordered — 4 sits before 5, which is perfectly valid.

Extracting repeatedly then gives the sorted order: swap the root with the last element, shrink, sift down. That is heap sort.

Two things this trace demonstrates. The build genuinely does little work — three sift operations for six elements, most of them trivial. And the array's final layout looks unsorted, which is the point: a heap is not a sorted structure, only a partially ordered one.

Sources and next steps

Run it in Python

A binary heap written from scratch on a plain list, then the same job handed to heapq. The point of the first half is that the tree is entirely imaginary — there are no nodes and no pointers.

heap.pyPython 3
Output
How the code works
  1. parent = (i - 1) // 2The tree exists only as arithmetic. A node at index i has its parent at (i-1)//2 and children at 2i+1 and 2i+2 — no pointers are stored, and none are needed.
  2. if self.a[parent] <= self.a[i]: breakA heap is a much weaker promise than a sorted list: each parent beats its own children, and nothing is claimed about siblings. That weakness is why push and pop cost O(log n) instead of O(n).
  3. last = self.a.pop(); self.a[0] = lastPopping the root leaves a hole, and the only item that can be removed without leaving a second hole is the last one. Moving it to the root and sifting down repairs the heap in one pass.
  4. if right < len(self.a) and self.a[right] < self.a[left]:Always sift towards the smaller child. Choosing the larger one makes it a valid-looking heap that returns wrong answers — a quiet bug rather than a crash.
  5. heapq.nlargest(3, data)Keeps a heap of size k rather than sorting everything: O(n log k). For “top 10 of a billion” that is the difference between practical and not.
Change one thing
  • Print h.a after all the pushes. It is not sorted — only a[0] is guaranteed, and expecting more is the usual misunderstanding.
  • Flip both comparisons to build a max-heap. Python's heapq has no max version, so real code pushes -value instead.
  • Push (priority, task) tuples where two priorities tie and the second item is not comparable. The TypeError is why production code pushes a counter as a tie-breaker.
Where this runs
Real CPython, compiled to WebAssembly and running on your own machine — nothing is uploaded. The first run takes a few seconds while the interpreter downloads; after that it is immediate. Need more room, or want to paste your own attempt? Use the Python compiler.




Predict, then reveal
About to run: double Heap type to 8. Before it does — what happens to the readout?
Committing to an answer first is the point — the reveal runs the experiment on the visualisation above and reads the real value back, so nothing here is scripted.
Check yourself
0 of 3
Answer without scrolling back up.
  1. In an array-backed heap, the children of index i are at:
  2. After several pushes, the underlying list is:
  3. heapq.nlargest(k, data) is O(n log k) rather than O(n log n) because it:





 Cheat sheet
Heaps and Priority Queues
Maintain a complete binary tree where the smallest element is always at the root, with O(log n) insert and extract-min.
ALGORITHMS · vizlearn.in/dsa/heaps_and_priority_queues.html
More in Algorithms
AlgorithmsHeap SortAlgorithmsTrie (Prefix Tree)AlgorithmsUnion-Find (Disjoint Set)AlgorithmsGraph Representations
About the author
Ashish Jangra builds and maintains VizLearn. Every module here is written and the visualisation behind it hand-built, so the numbers in a readout come from the same code that draws the picture. Corrections are genuinely welcome and get priority over everything else — if a page states something wrong, or an animation misrepresents what the algorithm does, get in touch.
About VizLearnGitHubLinkedInContact