3.3Priority queue operations
The idea
A priority queue serves the most important item first. A heap makes insert and extract O(log n) and peek O(1).
Think of it like this: An emergency room: the sickest patient is seen next, not the one who arrived first.
Why it exists
Priority queues sit behind heap sort, Dijkstra, Prim and top-k problems.
How it works
- Insert: add at the end, sift up.
- Extract: move the last element to the root, sift down.
- Peek: read the root.
- Top-k of n: keep a size-k heap, O(n log k).
Worked example: Find the 3 largest of 1,000,000 numbers
Keep a min-heap of size 3; each new number costs O(log 3), so the total is O(n), no sorting needed.
Now play with it
- →Read the table and note which operations are O(n).
- →Think about why searching an arbitrary key is O(n).
| Operation | Binary heap | Why |
|---|---|---|
| find-max (max-heap) | O(1) | the root |
| insert | O(log n) | add at the end and sift up: at most the height |
| extract-max | O(log n) | move the last element to the root and sift down |
| build from n items | O(n) | bottom-up heapify |
| search an arbitrary key | O(n) | no ordering between siblings |
| increase-key | O(log n) | sift up |
| k largest of n numbers | O(n log k) | keep a min-heap of size k |
| merge two heaps of size n | O(n) | concatenate and rebuild |
Heap sort = build (O(n)) + n extractions (O(n log n)) = Θ(n log n).
Check yourself
Which operation is NOT O(log n) in a binary heap of n elements?
Exam notes (the dense version)
insert is O(log n) (add at the end, sift up). extract-max is O(log n) (move the last element to the root, sift down). find-max is O(1). Searching an arbitrary key is O(n). Finding the k largest of n numbers: a min-heap of size k gives O(n log k). Merging two heaps by rebuilding costs O(n). A d-ary heap has height log_d n.
Previous year questions: Heaps & Priority Queues (9)
PYQs are grouped by topic, so this is the full set for Heaps & Priority Queues; try the ones that match this subtopic. Open all 9 on the topic page.