In a priority queue, top removes and returns the element with the highest priority. Unlike a plain queue, extraction follows priority rather than insertion order. section 10.3 section 10.22
A heap implements top by removing the root, which holds the highest-priority element. If other elements remain, the last array element moves to the root and is pushed down until the heap property is restored. section 10.18 section 10.22
Heap implementation
A Python top method raises ValueError for an empty heap, pops the sole element from a one-element heap, or replaces the root and calls _push_down before returning the removed element. The helper selects the higher-priority child while descending. section 10.18
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 top and insert across sorted arrays or linked lists, unsorted structures, and heaps. section 10.12
For a heap, top takes O(log n), because push-down follows at most one root-to-leaf path. Sorted structures can provide constant-time top, but their insertion cost is linear. section 10.12 section 10.5
