Priority Queue
A priority queue removes the item with the highest (or lowest) priority first, not necessarily the item that arrived first.
先从这个心智模型开始
A priority queue removes the item with the highest (or lowest) priority first, not necessarily the item that arrived first.
它如何工作，不堆砌不必要的术语
The abstract data type defines priority behavior; a heap is a common implementation.
It is useful whenever the 'most important next item' must be selected repeatedly.
把算法读成一连串决策
Identify the invariant that must always remain true.
Follow the read/update path through the structure.
After a mutation, restore the invariant before returning.
Read a tiny input by hand and write down the state after every important operation. For Priority Queue, the goal is to make the invariant visible rather than to memorize code.
insert/remove O(log n)
Do not quote this complexity mechanically. Ask which operation or input dimension it describes, then derive the cost from the loops, recursion depth, data-structure operations and any preprocessing assumptions.
适用场景
- Dijkstra/A*
- Schedulers
- Event simulation
通常哪里会出错
- Memorizing complexity without understanding representation.
- Ignoring worst-case shape or resizing/rebalancing costs.
专业回答结构
Differentiate the ADT from its implementation: priority queue describes behavior; binary heap is one efficient implementation.
What problem does Priority Queue solve?
A priority queue removes the item with the highest (or lowest) priority first, not necessarily the item that arrived first.
关于复杂度应该提到什么？
Its typical cost here is insert/remove O(log n), but a complete answer should connect that cost to the representation, input constraints and the dominant operations.
最常见的错误是什么？
Memorizing complexity without understanding representation.