At an emergency room, the next patient may be the one who needs care most urgently, not the one who arrived first. A priority queue handles this kind of changing order: it returns items by priority rather than simply by arrival time. section 10.1
A priority queue offers two core operations:
- insert adds an element. section 10.3
- top removes and returns the highest-priority element. The name may differ in other interfaces. section 10.3
Which bug gets fixed next?
Suppose bugs are marked desired, needed, urgent, or critical. A regular queue returns the oldest bug; a priority queue returns the most urgent one. A newly reported critical bug need not wait at the rear. section 10.2
Priority describes what the queue must return, not how it stores items. One implementation keeps items sorted by priority; another searches for the highest-priority item when needed. A binary heap provides a more efficient choice: its highest-priority item is at the root, and an array-backed heap supports logarithmic-time insert and top. An existing array can also be turned into a heap in linear time. section 10.4 section 10.22
