What operations define the priority queue abstraction, and how does it differ from a FIFO queue?
answer
- Think about what you can ask the container
- Only one element is characterized at a time
- Two removal-rule cousins decide by arrival time
- Three operations: put in, look, take
- Contract, not container: peek and extract-top
basics
~20 sA priority queue supports three operations: insert an item with a priority, peek at the top-priority item, and extract that item. A FIFO queue hands back items in arrival order; a priority queue hands back the most urgent one first.
solid answer
~50 sThe priority queue is an *abstract data type* defined by three operations: `insert(item)` places an item with an associated priority, `peek()` reports the current top-priority item without removing it, and `extract-top()` removes and returns it. Ordering comes from a comparison rule you supply, not from arrival time — that is the whole difference from a FIFO queue, which promises first-in-first-out and nothing about content. Just as important is what the abstraction does *not* promise: the elements are not kept fully sorted, iterating the container gives no meaningful order, there is no positional or index access, and searching for or removing an arbitrary item is not a cheap operation. In a support desk, that is exactly the contract you want for "give me the next ticket to work" — and exactly the wrong one for "show me all open tickets in order".
go deeper
Be ready to name the three operations — insert, peek, extract-top — and say in one sentence that ordering comes from a comparison rule rather than arrival time. Say out loud that the container is not kept sorted.
Explain the ADT-versus-implementation split: the same contract can sit on a heap, a sorted array or an unsorted list, and the operation costs belong to the backing choice, not to the abstraction.
Show where the contract stops in a real system: dispatch uses the queue, while browsing and cancellation need a separate index. Interviewers look for the candidate who names what the abstraction refuses to promise.
Own the design call of what belongs behind a priority queue interface at all. Teams reach for one when they actually need an ordered listing or cancellations, and end up bolting a second structure onto it anyway.
## The abstraction, not the implementation A priority queue is an **abstract data type (ADT)**: a contract of operations and their meanings, with no commitment to how they are realized. Confusing it with a binary heap is the single most common slip on this topic. The heap is *one* way to satisfy the contract; a sorted array, a balanced search tree, or an unsorted list all satisfy the same contract at different costs. ## The core operations Three operations define it: - **insert(item)** — add an item; the item carries, or can be compared on, a priority. - **peek()** — return an item of top priority *without* removing it. Undefined (or an error) on an empty queue. - **extract-top()** — remove and return an item of top priority. Two more are universally present but carry no interesting semantics: **size()** and **is-empty()**. Some designs add **bulk build** (turn n existing items into a queue in one step, which is cheaper than n separate inserts) and **merge** (combine two queues) — those are extensions, not part of the minimum contract. Notice the wording of extract-top: it returns *an* item of top priority, not *the* item. When several items tie on priority, the contract deliberately leaves the choice open. That looseness is what buys the cheap implementations. ## What it deliberately does not promise Being precise about the negative space is what separates a candidate who has used the abstraction from one who has read about it: - **The contents are not sorted.** Only the top is characterized. Everything below it is in whatever arrangement the implementation finds convenient. - **Iteration order is meaningless.** Walking the container does not visit items in priority order. If you need a sorted listing, you drain the queue, or you use a different structure. - **No positional access.** There is no "third item" — the concept does not exist in the contract. - **No cheap search or arbitrary removal.** Finding a specific item generally means scanning everything. - **No arrival-order guarantee**, not even among items of equal priority. ## Against a FIFO queue and a stack All three are "put things in, take things out" containers that differ only in the removal rule: | ADT | Removal rule | Ordering comes from | |---|---|---| | FIFO queue | oldest first | arrival time | | Stack (LIFO) | newest first | arrival time | | Priority queue | most urgent first | a comparison rule over the items | A FIFO queue and a stack decide by *when* an item arrived; a priority queue decides by *what the item is*. That is why a priority queue needs an ordering rule supplied from outside and the other two do not. It is also why a priority queue can be made to imitate a FIFO queue — give every item the same priority and break ties on an increasing arrival counter — while a FIFO queue can never imitate a priority queue. ## A worked setting A support desk stores tickets as `{tier, created_at, id}`, tier 1 being the most urgent. Dispatching agents ask the system for the next ticket to work. That request is exactly `extract-top()`. A dashboard asking "what would be dispatched next, without taking it" is exactly `peek()`. A new ticket arriving is `insert()`. Nothing else in the contract is needed to run the desk. What the desk *cannot* get from the same structure: a paginated "all open tickets, most urgent first" screen (that is a sorted listing, which the abstraction does not offer), or "cancel ticket 4712" (arbitrary removal, which the abstraction does not offer cheaply). Real systems keep the priority queue for dispatch and a separate index for browsing and cancellation. Recognizing that split is the point of learning the contract. ## Typical costs With the usual array-backed binary heap behind it: `peek` is O(1), `insert` and `extract-top` are O(log n), and bulk-building from n items is O(n). These are properties of *that* implementation, not of the ADT — an unsorted list would give O(1) insert and O(n) extract and still be a perfectly legal priority queue. Quote the operation costs together with the backing choice, never as though the abstraction itself fixed them.
- Can you get the second-most-urgent item cheaply from a priority queue?Not through the contract — `peek` characterizes only the top. You would extract the top, read the new top, then put the first one back. With a binary heap behind the queue you happen to know the runner-up is one of the root's two children, but that is an implementation fact you are not entitled to rely on through the abstraction.
- If every item is inserted before any is removed, do you still want a priority queue?Often not. Build-once-drain-once has no interleaving, so you can sort the whole batch once and walk it, which is simpler and gives you a browsable ordered list for free. The priority queue earns its keep when inserts and extractions interleave and the set is changing while you consume it.
A FIFO queue is the line at a bakery; a priority queue is a hospital triage desk. Both take everyone in, but only one of them decides who goes next by how urgent they are.
saying these in an interview costs you the question
- Says a priority queue is just another name for a heap
- Claims the container keeps all elements fully sorted
- Expects iterating the queue to visit items in priority order
- Confuses peek with extract-top
- Assumes finding an arbitrary item in it is cheap