Card 09/ 09
Recap: Heaps
Two properties, two sifts, a linear build, and each language's own priority queue.
Heaps come down to the seven ideas below, each listed with the card that covers it. Two properties, heap order and a complete shape, explain all of them: the order puts the smallest item at the root, and the shape lets the tree live in an array and keeps every path about log2 n long.
| The idea | Where |
|---|---|
Every parent is no larger than its children, the tree fills level by level, and the parent of index i is at (i - 1) // 2; a heap is not sorted | Heaps: A Complete Tree Stored in an Array |
| Push appends and sifts up; pop moves the last item to the root and sifts down towards the smaller child; both are O(log n) | Push and Pop With Sift-Up and Sift-Down |
| Sifting down every parent from the last one back to the root builds a heap in O(n) | Build a Heap Bottom-Up in Linear Time |
| n pushes cost O(n log n) in the worst case and leave a different array; heapify when all items are known | Building a Heap With n Pushes |
Python's heapq works on a list, Java's PriorityQueue takes a comparator and iterates in array order, and TypeScript has no heap | Binary Min-Heap in Python, Java and TypeScript |
heapq pops the smallest item, so a largest-first queue pushes negated keys | Treating Python's heapq as a Max-Heap |
| A heap suits interleaved inserts and removals; a sorted array suits items read in order | Heap vs Sorted Array for a Priority Queue |
The picture to keep is one heap seen two ways, as a tree and as the array that stores it. Reading the tree level by level, left to right, gives the array 1 3 5 7 4 8.
1, index 0
3, index 1
7, index 3
4, index 4
5, index 2
8, index 5
null, index 6, the next free position
Together they let you push into and pop from a heap by hand, build one from unordered items in linear time, use each language's priority queue in either direction, and decide when a heap beats a sorted array.
← → move through sections and cards