After this lesson, you will be able to: Understand the heap property, implement insertion and extraction with heapify, and use heaps for priority queues and heap sort.
A heap is a tree-shaped structure with one job: give you the smallest (or largest) element instantly. It is the engine behind priority queues, the top-K pattern, and Dijkstra's algorithm.
A binary heap is a complete binary tree (filled left to right, no gaps) with one rule. In a min-heap, every parent is smaller than or equal to its children, so the smallest value is always at the root. In a max-heap, every parent is larger, so the largest is at the root. The heap does not fully sort the data; it just guarantees the extreme element is on top, and that is exactly what a priority queue needs.
No node objects needed. Parent/child relationships are index math.
# For a node at index i (0-based):# left child = 2*i + 1# right child = 2*i + 2# parent = (i - 1) // 2# Python's heapq is a min-heap on a plain listimport heapqh = []heapq.heappush(h, 5)heapq.heappush(h, 1)heapq.heappush(h, 3)smallest = heapq.heappop(h) # 1, in O(log n)# Max-heap trick: push negated valuesmaxh = []heapq.heappush(maxh, -5)heapq.heappush(maxh, -1)largest = -heapq.heappop(maxh) # 5
To insert, put the new value at the end of the array, then sift it up: swap it with its parent while it violates the heap property. To extract the root (the min or max), swap it with the last element, remove that last element, then sift the new root down: swap with the smaller child while it violates the property. Both operations touch one path from root to leaf, so both are O(log n). Reading the top without removing is O(1).
Sorting falls out of the heap for free.
1. Push all n elements into a min-heap: O(n log n).
2. Pop them one at a time. Each pop returns the next smallest.
3. The pops come out in sorted order. Total: O(n log n).
4. (Advanced) In-place heap sort builds a max-heap in the array and repeatedly swaps the root to the end, using no extra memory.
5. Verify your output is sorted for [5,1,3,2,4].
Confusing a heap with a BST (a heap only orders parent vs child, not left vs right, so you cannot binary-search it). Trying to find an arbitrary element in a heap quickly (that is still O(n); heaps are only fast at the extreme). Forgetting Python's heapq is a min-heap and not negating values when you need a max-heap. Sorting the whole array when a size-K heap would be faster for top-K. Breaking the complete-tree shape and then wondering why the index math fails.
Sign in and purchase access to unlock this lesson.