Suppose a bug tracker receives reports in one order but must address the most severe bug next. A plain queue serves reports by arrival time; a sorted list can serve them by severity, but maintains more ordering than the task requires. A priority queue stores each report with a priority and guarantees that the next extracted report has the highest priority, regardless of insertion order. section 2.3.1 section 2.4.1 section 2.4.2
Its API separates what callers can rely on from how the ordering is maintained:
- insert(element, priority) adds an item; update(element, newPriority) changes its priority; remove(element) deletes a specified item. section 2.4
- peek() returns the highest-priority item without removing it; top() returns and extracts it; size() reports the item count. section 2.4
Serve the next bug
Insert five bug reports with severity scores 7, 9, 1, 8, and 5. The first call to top() extracts the severity-9 report, leaving four items. The next extracts the severity-8 report. Their insertion positions do not determine the result. section 2.4.1
A priority queue is an abstract data structure, not a particular storage layout. An unsorted array makes insertion cheap but leaves work for extraction. A sorted array does the ordering work on insertion. A heap instead keeps a partial order: in a binary heap, each node has higher priority than its children, so the top item is at the root. The complete, left-adjusted tree fits compactly in an array; with zero-based indices, node i has children at 2i + 1 and 2i + 2, and a non-root node has parent at ⌊(i − 1)/2⌋. A heap can also be oriented to return the lowest-priority item first. section 2.4 section 2.5.2 section 2.5.3
Table 2.2 Performance for operations provided by PQs, broken bown by underlying data structure (view table figure)
| O(1) a |
O(1) a |
||
| O(n) b |
O(1) c |
Compare insertion, finding the next item, and extracting it across arrays and balanced trees. The unsorted-array constant-time lookup assumes an extra tracked minimum; deleting that minimum can still take linear time. section 2.5.2
Choose an implementation for the operations the application actually performs. Priority queues can support logarithmic-time operations without keeping a full sort, but a cheaper insertion may mean a slower extraction. They also serve as supporting structures: a heap can help find the k largest elements using O(n + k log k) comparisons and swaps and O(k) extra space, particularly when k is much smaller than n. Priority queues are also used in shortest-path algorithms and to select entries for LFU cache eviction; in those settings, implementation costs can affect the larger algorithm. section 2.3.1 section 2.5.2 section 2.7 section 2.8.1
