Goal: Use a min-heap to repeatedly extract the smallest available item in logarithmic time.

The Min-Heap property

In a min-heap, the smallest value is always at the top. When you remove it, the heap quietly reorganises itself in about log n steps so the next smallest value rises to the top.

It is like a tournament ladder: when the champion leaves, a few matches decide the new one, without replaying the whole tournament.

Reading the top: is instant.

Push and pop: take about log n steps to restore the order.

In code

import heapq
nums = [5, 2, 8]
heapq.heapify(nums)
smallest = nums[0]

nums = [7, 10, 4, 3, 20, 15], k = 3 · index i's children are at 2i + 1 and 2i + 2

The array drawn as a tree: index 0 on top, then 1 and 2, then 3, 4, 5. No pointers, just positions. It isn't a heap yet.

Move 1 of 5

Heaps across languages

Every language ships a ready-made heap, so you rarely write one yourself. In Python, the heapq module turns a list into a min-heap and pops from it. In C++, the priority queue with a "greater" comparison is a min-heap. In Java, a PriorityQueue is a min-heap by default.

Learn the one in your language and you'll reuse it on many problems.

Python: the heapq module works on plain lists.

C++: the priority queue needs a greater comparison to act as a min-heap.

Java: PriorityQueue is a min-heap by default.