Unit 17: Heaps and Priority Queues
A tree that only promises its smallest or largest value sits on top, and the two moves, sift up and sift down, that keep that promise.
5 topics · 17 questions
Each topic is a path, not a menu: work down it in order and every question builds on the one above. Click any of them to watch the answer draw itself.
The Heap Property and Its Array Representation
- How it worksHow does a min-heap store a complete binary tree inside a single flat array with no pointers at all?
- Worked exampleFind the parent, left child, and right child indices for the element at index 3 in an array-backed heap.
- Common mistakeWhy isn't a heap the same thing as a fully sorted array?
Your turn1 of 2
In an array-backed heap, the element at index 696 has its left child at index 2i+1 and right child at index 2i+2. What is the index of the left child of the element at index 696?Sift-Up: Restoring the Heap After an Insert
- How it worksHow does sift-up repeatedly swap a new element with its parent until the heap property holds again?
- Worked exampleTrace inserting 2 into the min-heap [5, 8, 6] and follow it sifting up to its correct position.
- Going furtherWhat happens during sift-up when the newly inserted value is already larger than its parent?
Your turn1 of 2
A newly inserted value sifts up by swapping with its parent 14 times before settling into its correct position. How many total swaps does this sift-up operation perform?Sift-Down: Restoring the Heap After Extract-Min
- How it worksHow does sift-down repeatedly swap a misplaced element with its smaller child until it settles into place?
- Worked exampleTrace extract-min on the min-heap [2, 5, 6, 8] and follow the last element sifting down after replacing the root.
- Common mistakeWhy doesn't extracting the minimum from a heap just remove it and shift everything else forward by one?
- Going furtherWhat happens during sift-down when the element being moved down has two children holding different values?
Your turn1 of 2
Sift-down repeatedly swaps a misplaced element with its smaller child until it settles, taking 14 swaps this time. How many total swaps does this sift-down operation perform?Building a Heap from an Unordered Array
- How it worksHow does heapify sift down every non-leaf node starting from the middle of the array and working back to the front?
- Worked exampleTrace heapify on the array [4, 10, 3, 5, 1] and find the resulting min-heap order.
- Going furtherWhat changes about the total work once heapify processes an array of a million elements instead of five?
Your turn1 of 2
Heapify processes every non-leaf node in an array of 696418 elements, starting from the middle and working back to the front, visiting roughly n over 2 non-leaf nodes. About how many non-leaf nodes does heapify process?Priority Queue Applications
- How it worksHow does a priority queue always hand back the highest-priority item first no matter what order items were added in?
- Worked exampleTrace a priority queue processing patients with priorities 3, 1, 4, 1 and find the order they get treated in.
- Going furtherWhat changes about a priority queue's behavior once two items are inserted with the exact same priority?
- Ties togetherHow does Dijkstra's shortest path algorithm depend on a priority queue to expand the closest unvisited node next?
Your turn1 of 2
A priority queue processes 697 items in total, always handing back the highest-priority item first regardless of insertion order. How many total items does the priority queue hand back across all n extractions?