BeginnerTopic 24 of 104Software & Computing
Heaps and priority queues
Quickly access the smallest or largest element.
In depth
A binary heap is a complete tree stored in an array where each parent is ≤ (min-heap) its children. Insert and extract-min are O(log n), peek is O(1). Priority queues support Dijkstra's algorithm, scheduling and top-k problems. Heap sort uses a heap in O(n log n).
Key points
- Sift up and sift down
- Build-heap in O(n)
- Fibonacci heaps theory
ExampleAn OS scheduler picks the highest-priority ready task from a priority queue.
What is Heaps and priority queues?
Quickly access the smallest or largest element.
Why is it important to understand heaps and priority queues?
Heaps give quick access to the smallest or largest item, which is what schedulers and shortest-path algorithms need.
What is the heap property?
In a min-heap each parent is smaller than or equal to its children, so the minimum sits at the root.
What is the cost of insertion?
Insertion and removal take logarithmic time, while peeking at the top item takes constant time.
How is Heaps and priority queues used in practice?
Typical applications include picking the next job with the highest priority in a task scheduler, finding the k largest values in a large stream and driving the event queue in a discrete event simulation.
What should I learn before Heaps and priority queues?
Study "Balanced trees" first (topic 23 of 104 in Software & Computing). It covers the groundwork this topic builds on.
What are the key points of Heaps and priority queues?
Sift up and sift down. Build-heap in O(n). Fibonacci heaps theory.
Can you give an example of Heaps and priority queues?
An OS scheduler picks the highest-priority ready task from a priority queue.
What comes after Heaps and priority queues?
The next topic is "Graphs", which builds directly on this one.
How difficult is Heaps and priority queues?
It is classed as Beginner in Software & Computing (topic 24 of 104). It is an entry-level topic. It relies only on basic school mathematics and the ideas introduced earlier in this discipline.