The heap and the priority queue
The priority queue as an abstract type and the binary heap that implements it: heap property, complete tree stored in an array (parent and child indices), insertion by sifting up, extraction by sifting down, costs.
- 22 cards
- 5 topics
- Free
The outline, topic by topic
Each topic is weighted the way the exam weighs it.
- Concepts
- Questions
- Sort and link
- Scenarios
- Understand
A few cards from the deck
Priority queue: what is it?
Show the answer
A collection where elements with a priority are added and the one with the highest priority is always removed, whatever the order of arrival.
Unlike an ordinary queue (first come, first served), the order of exit depends on priority. A heap implements it with insertion and extraction in O(log n).
The min-heap is
[2, 5, 3, 9, 6]. We insert 1. What is the resulting array?[1, 5, 2, 9, 6, 3][1, 2, 3, 9, 6, 5][2, 5, 3, 9, 6, 1][1, 2, 5, 3, 9, 6]
Show the answer
[1, 5, 2, 9, 6, 3]1 lands at index 5, whose parent is at index 2 (value 3): swap. It is then at index 2, whose parent is at index 0 (value 2): another swap. Result: 1 at the root, 2 at index 2 and 3 at index 5.
In a min-heap, the smallest element is always at the …, so at index … of the array.
Show the answer
In a min-heap, the smallest element is always at the root, so at index 0 of the array.
Reading the minimum therefore costs O(1). Extracting it costs O(log n), since the heap property then has to be restored.
Binary heap: what is it?
Show the answer
A complete binary tree, filled level by level from left to right, where each node is smaller than its children (min-heap) or larger (max-heap).
Only the root is known to be the smallest (or the largest); siblings are not ordered relative to each other. A heap is not a sorted array.
A scheduler holds 200,000 waiting tasks. On each new task, it re-sorts the whole list by urgency, then runs the most urgent one. The server is overloaded. Which fix?
- Keep the tasks in a heap ordered by urgency
- Sort with a faster sort on each new task
- Only re-sort on one arrival in ten
- Keep the tasks in a sorted linked list
Show the answer
Keep the tasks in a heap ordered by urgency
A full sort costs O(n log n) on each arrival, when only the most urgent task is wanted. A heap gives it in O(1), extracts it and takes a new task in O(log n). A sorted list would insert in O(n); a faster sort keeps the useless work, a less frequent one sometimes runs the wrong task.