15 MIN GUIDE · INTERMEDIATE · HEAPS & PRIORITY QUEUES

Heaps and Priority Queues

How a binary heap keeps the most urgent item at the front, supports fast updates, and powers efficient priority queues.

When ordinary queues are not enough

A normal queue serves items in arrival order. A priority queue serves the item with the smallest or largest priority first. An emergency desk, for example, handles the most urgent case rather than the earliest arrival.

A binary heap is the usual way to implement a priority queue. A min-heap follows one rule: every parent is no greater than either child. Therefore the minimum is always at the root. A max-heap reverses the rule and keeps the maximum at the root.

The rule does not fully sort the data. Siblings may appear in either order, and values on different branches cannot be compared by position alone. This weaker promise is exactly what makes updates fast.

A tree stored in an array

A heap is a complete binary tree: every level is full except possibly the last, which fills from left to right. That shape fits into an array without pointers. For an item at index i:

its parent is at (i - 1) // 2,
its left child is at 2i + 1,
its right child is at 2i + 2.

For the array [2, 5, 4, 9, 8, 7], the root is 2. Its children are 5 and 4; the children of 5 are 9 and 8.

Insert 3 into a min-heap

Start
The heap rule holds

Heap

254987

minimum = 2

Read the minimum at index 0.

The two repairs

Insert appends the new value, then sifts up while it is smaller than its parent. Remove minimum replaces the root with the last value, removes the last slot, then sifts down by swapping with the smaller child.

Operation	Time	Reason
Peek at minimum	O(1)	Read index 0
Insert	O(log n)	Move up at most one tree height
Remove minimum	O(log n)	Move down at most one tree height
Build from n values	O(n)	Sift down internal nodes from the bottom
Find an arbitrary value	O(n)	The heap is not fully sorted

Common mistake.

Sorting after every insertion makes a priority queue unnecessarily expensive. Restore only the heap rule.

Building a min-heap

The program inserts tasks as (priority, name) pairs. A smaller number means greater urgency. A sequence number breaks ties by arrival order, so equal-priority tasks behave predictably.

import heapq

tasks = []
sequence = 0


def add(name, priority):
    global sequence
    heapq.heappush(tasks, (priority, sequence, name))
    sequence += 1


add("revise graphs", 3)
add("submit project", 1)
add("practise arrays", 2)
add("join class", 1)

print("next:", tasks[0][2])
while tasks:
    priority, _, name = heapq.heappop(tasks)
    print(priority, name)

Output

next: submit project
1 submit project
1 join class
2 practise arrays
3 revise graphs

Choosing the right structure

Use a heap when work repeatedly asks for the next minimum or maximum while items are still being added. If all values are known and every value must be visited in order, sorting once is usually simpler. If priorities can change, store an identifier with each entry and carefully handle stale entries or use a heap implementation that supports key updates.