Heaps & Priority Queues

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

References

• ↗ https://www.php.net/manual/en/class.splminheap.php

Tags

Related Terms