In PHP, how would you serve support tickets by severity with SplPriorityQueue, and what ordering does it not guarantee?
answer
- a max-heap underneath
- insert($value, $priority)
- EXTR_DATA is the default extract flag
- equal priorities: order undefined
- iteration extracts as it goes
basics
~20 sCall insert($ticket, $severity) and extract() in a loop: SplPriorityQueue is a max-heap, so the highest severity comes out first. Tickets with equal severity come out in undefined order, so add a sequence number to the priority when first-come-first-served matters.
solid answer
~40 s`SplPriorityQueue` is a binary heap. `insert($ticket, $severity)` stores the ticket with its priority; `extract()` removes and returns the element whose priority compares **highest**, and `top()` peeks without removing. By default `extract()` returns only the data; `setExtractFlags(SplPriorityQueue::EXTR_BOTH)` returns `['data' => …, 'priority' => …]`. The catch interviewers look for is that **equal priorities come out in undefined order**, not insertion order. For support tickets that means two critical tickets may be served newest first. The fix is a composite priority such as `[$severity, -$sequence]`: arrays of the same size compare element by element, so severity decides first and the lower sequence number wins ties. Also remember that iterating the queue, or passing it to `iterator_to_array()`, extracts every element, and `extract()` on an empty queue throws `RuntimeException`.
code
php · 13 lines<?php
declare(strict_types=1);
$queue = new SplPriorityQueue();
$seq = 0;
foreach ([['T-1', 2], ['T-2', 4], ['T-3', 4], ['T-4', 1]] as [$id, $severity]) {
// severity first; on a tie, the lower sequence (older ticket) wins
$queue->insert($id, [$severity, -$seq++]);
}
while (!$queue->isEmpty()) {
echo $queue->extract(), ' '; // T-2 T-3 T-1 T-4
}go deeper
Know insert($value, $priority), extract() and top(), and that the largest priority comes out first.
Explain the heap underneath, why equal priorities come out in undefined order, and how a composite [severity, -sequence] priority restores first-come-first-served.
Catch destructive iteration and the empty-heap exception in worker code, and make priorities unique so fairness holds under load.
Weigh an in-process priority queue against a durable queue with priority support, given restarts, multiple workers and starvation of low-severity work.
## What SplPriorityQueue is `SplPriorityQueue` is the SPL's **binary heap** of `(data, priority)` pairs. A heap keeps the "largest" element at the top and restores that property on every insert and removal, each in logarithmic time. It is the right structure whenever the next item to process is the one with the highest priority, not the one that arrived first. The core methods: | Method | Effect | |---|---| | `insert(mixed $value, mixed $priority)` | add an element | | `extract()` | remove and return the top element | | `top()` | return the top element without removing it | | `count()`, `isEmpty()` | size checks | | `setExtractFlags(int $flags)` | choose what `extract()` and `top()` return | | `compare(mixed $priority1, mixed $priority2)` | override to change the ordering | ## Serving tickets by severity For a help desk where severity 4 is critical and 1 is low: 1. On arrival, `insert($ticket, $ticket->severity)`. 2. A worker loops `while (!$queue->isEmpty()) { handle($queue->extract()); }`. 3. The highest severity always comes out next, however long the queue is. Priorities are compared with PHP's ordinary comparison, and the default `compare()` returns a positive number when the first priority is greater, which places it nearer the top. So larger numbers win. To serve the **smallest** first, either insert negated priorities or subclass and override `compare()` to return `$priority2 <=> $priority1`. ## Extract flags - `SplPriorityQueue::EXTR_DATA` (the default): return the value only. - `SplPriorityQueue::EXTR_PRIORITY`: return the priority only. - `SplPriorityQueue::EXTR_BOTH`: return an array with the keys `data` and `priority`. Passing `0` throws `RuntimeException` ("Must specify at least one extract flag"). ## The ordering it does not guarantee The manual states it plainly: the order of elements with **identical priority is undefined**. A heap does not remember insertion order, so two severity-4 tickets inserted at 09:00 and 09:05 may come out in either order. For support work that is a fairness bug: under load, an early critical ticket can keep losing to later ones. The fix is to make every priority unique and ordered the way you want: - **Composite array priority**: `insert($ticket, [$severity, -$sequence])`, where `$sequence` increments on every insert. Two arrays with the same number of elements compare element by element, so severity decides first; on a tie, `-5` is greater than `-9`, so the older ticket (sequence 5) wins. - **Single integer**: `insert($ticket, $severity * 1_000_000 - $sequence)`, if you can bound the sequence. ## Choosing the priority type Because priorities are compared with PHP's ordinary comparison, their **type** matters: - **Integers** are the safe default: `4 > 2` means what it says. - **Severity labels as strings** are a trap. Non-numeric strings compare byte by byte, so `'critical'` sorts below `'low'` and the queue serves low-severity tickets first. Map labels to integers before inserting, for example with a backed enum's `->value`. - **Arrays** compare by element count first and then element by element, which is what makes `[$severity, -$sequence]` work; keep every priority array the same length. - **Enum cases or other objects** are not a useful priority: two different enum cases are not ordered by `<` or `>`, so the heap has nothing meaningful to compare. Insert the enum's backing value instead. ## Iteration is destructive `SplPriorityQueue` implements `Iterator`, but iterating **extracts**: each step of a `foreach` removes the top element. A `foreach` for logging, a `var_dump` of `iterator_to_array($queue)`, or a helper that "just counts" by iterating will leave the queue empty. To inspect without draining, iterate a `clone`. Other behaviour worth knowing: - `extract()` and `top()` on an empty queue throw `RuntimeException` ("Can't extract from an empty heap", "Can't peek at an empty heap"). - The queue is an object, so passing it to a function shares the same heap; the function's `extract()` calls are visible to the caller. - If a custom `compare()` throws, the heap is marked corrupted and further operations throw until `recoverFromCorruption()` is called. ## Related classes `SplMinHeap` and `SplMaxHeap` order plain values without a separate priority, and `SplHeap` is their abstract base with a `compare()` to implement. Use them when the value itself is the ordering key; use `SplPriorityQueue` when the payload and its priority differ, as a ticket and its severity do.
- How do you look at every ticket in the queue without emptying it?Iterate a copy: `foreach (clone $queue as $ticket)`. Iterating an `SplPriorityQueue` extracts elements, so a loop over the original drains it. Cloning copies the heap, and the copy is consumed instead. `top()` alone shows the next ticket without removing it.
- How do you make SplPriorityQueue serve the lowest priority first?Either insert negated priorities, or subclass it and override `public function compare(mixed $priority1, mixed $priority2): int` to return `$priority2 <=> $priority1`. The default comparison puts larger priorities on top; reversing it turns the structure into a min-first queue.
saying these in an interview costs you the question
- Tickets with equal priority come out in insertion order
- extract() returns the lowest priority first by default
- A foreach over the queue leaves its elements in place
- extract() on an empty queue returns null
- EXTR_DATA returns both the value and its priority