Imagine a bug queue where a broken login needs attention before a minor display glitch, regardless of which report arrived first. A binary heap keeps the highest-priority item ready to remove without keeping every item fully sorted. section 10.0 section 10.16
A binary heap is an almost complete binary tree: each node has at most two children, every level but possibly the last is full, and the last level fills from left to right. Each node has priority at least as high as its children, so the root has the highest priority in the whole heap. Paths from root to leaf are ordered, but the heap is not a fully sorted collection. section 10.10 section 10.11
An array, such as a Python list, holds the tree while these operations maintain its properties:
- Insert: append the item at the end, then move it toward the root while it outranks its parent. section 10.17
- Top: remove and return the root, move the last item into its place, then push that item down past a higher-priority child until the ordering is restored. section 10.18
- Heapify: turn an existing, unordered array into a heap by pushing down internal nodes, working backward from the last one. This takes O(n) time. section 10.19
A new urgent bug
Suppose ("Broken Login", 9) is appended to a bug heap. If its priority exceeds its parent’s, it moves upward; it keeps moving until it reaches the root or a parent with at least as much priority. Appending first preserves the tree’s shape, while moving upward repairs its priority order. section 10.17
Table 10.2 An updated comparison of various implementations of a priority queue (view table figure)
| insert() |
top() |
|
|---|---|---|
| Sorted array/linked list |
O(n) |
O(1) |
| Unsorted array/linked list |
O(1) |
O(n) |
| Heap |
O(log(n)) |
O(log(n)) |
Compare the costs of insert and top: the heap balances both at O(log n), whereas sorted and unsorted arrays or linked lists make one operation O(n). section 10.12
The almost complete shape keeps a heap’s height proportional to log n. Insert and top each follow at most one root-to-leaf path, giving both operations O(log n) time. Use a heap when priority determines what comes out next and neither operation should bear the linear-time cost of a simpler array or linked-list implementation. section 10.11 section 10.12
