CSCI2100 · Theorem · Chapter 3 · Priority queues
Removing a minimum
2 steps of prerequisites below it
Returning the root, moving the last key to the root and repeatedly swapping it with a smaller child returns a minimum and leaves a min-heap of the remaining keys.
Taught in
- 3.1 Binary min-heaps and priority queues · introduced
Uses
- Binary min-heap · used in its proof, proof step 3.1
Used by
No later knowledge point in these notes uses it.
Counterexamples
Everything this builds on, earliest first · 2 steps
Each step comes after its own prerequisites, so reading in this order never needs something you have not met. It is a reading order for these notes, not a diagnosis of what you know.
- Min-priority queue · 3.1
- Binary min-heap · 3.1
Possible roots and a review route need your own answers on these points. None are recorded yet, so none are suggested.
Longest chain down to a starting point
Each step is used by the one above it, across courses where the notes link them. It ends at a point the notes define without another point.