Heaps & Priority Queues
debt(d7/e3/b3/t5)
Closest to 'only careful code review or runtime testing' (d7). The detection_hints indicate automated detection is 'no' and the only listed tool is Blackfire (a profiler), meaning the misuse — using array+sort() instead of a heap — is invisible until performance is measured under load. A linter will not flag it; it requires profiling or attentive code review to spot the O(n log n) vs O(log n) pattern difference.
Closest to 'simple parameterised fix' (e3). The quick_fix states: replace array+sort() with SplMinHeap or SplMaxHeap. This is a contained refactor — swap out the data structure and update insertion/extraction call sites — but it likely touches a few methods in one component rather than a single-line patch, putting it at e3 rather than e1.
Closest to 'localised tax' (b3). The misuse is typically confined to one component (a scheduler, event loop, or pathfinding routine). The rest of the codebase is unaffected; only the code using the priority queue pays the performance penalty. The applies_to scope (web, cli) is broad, but actual heap usage is concentrated, so the structural burden is localised.
Closest to 'notable trap' (t5). The misconception field explicitly states: 'A sorted array is a good priority queue' — a documented gotcha that most developers eventually learn. Additionally, the common_mistakes note that SplMaxHeap vs SplMinHeap confusion (getting largest when you wanted smallest) is a real gotcha. These are well-known but non-obvious surprises, fitting t5.
Also Known As
TL;DR
Explanation
A binary heap is a complete binary tree stored in an array. For node at index i: left child at 2i+1, right at 2i+2, parent at (i-1)/2. Heapify maintains the heap property in O(log n). Building a heap from n elements is O(n) — not O(n log n). Priority queue applications: task scheduling, Dijkstra's algorithm, Huffman coding, event simulation. PHP's SplMinHeap and SplMaxHeap implement min and max heaps respectively.
Diagram
flowchart TD
subgraph Min_Heap
ROOT2[1 - root always minimum]
ROOT2 --> L3[3]
ROOT2 --> R3[2]
L3 --> LL2[7]
L3 --> LR2[4]
R3 --> RL2[5]
end
INSERT[insert 2] -->|add at end then bubble up| ROOT2
EXTRACT[extract min] -->|remove root move last to top sink down| ROOT2
subgraph Complexity
INS_C[insert: O of log n]
EXT_C[extract min: O of log n]
PEEK[peek min: O of 1]
end
style ROOT2 fill:#238636,color:#fff
style INS_C fill:#1f6feb,color:#fff
Common Misconception
Why It Matters
Common Mistakes
- Using array + sort() as a priority queue — O(n log n) per insertion vs O(log n) for a heap.
- Not understanding that a heap is not fully sorted — only the root is guaranteed to be the min/max.
- Using SplMaxHeap when SplMinHeap is needed — SplMaxHeap returns the largest element, not the smallest.
- Reinventing a priority queue with array sorting in PHP when SplMinHeap exists.
Code Examples
// Array as priority queue — O(n log n) per operation:
$queue = [];
foreach ($tasks as $task) {
$queue[] = $task;
usort($queue, fn($a, $b) => $a['priority'] <=> $b['priority']); // O(n log n) each!
}
$next = array_shift($queue); // O(n) reindex// SplMinHeap — O(log n) insert, O(1) peek, O(log n) extract:
class TaskHeap extends SplMinHeap {
protected function compare(mixed $a, mixed $b): int {
return $b['priority'] <=> $a['priority']; // Lower number = higher priority
}
}
$heap = new TaskHeap();
foreach ($tasks as $task) $heap->insert($task); // O(log n)
$next = $heap->top(); // O(1) peek
$next = $heap->extract(); // O(log n) extract