Heaps and priority queues — SplMinHeap, SplMaxHeap

Advanced5 min read·eng-07-005

compare

Concept

Heap: A complete binary tree that satisfies the heap property:

Min-heap: Parent ≤ children. The root is always the minimum element.
Max-heap: Parent ≥ children. The root is always the maximum element.

Key operations (all O(log n) except peek):

insert: Add to the bottom, "bubble up" (sift up) to restore the heap property.
extract (pop min/max): Remove root, put the last element at root, "bubble down" (sift down).
peek (top): O(1) — just read the root.
heapify: Build a heap from an array — O(n) (more efficient than n inserts).

Why heaps: When you need the min or max element repeatedly, but items are added dynamically. Examples: Dijkstra's algorithm, A* pathfinding, Huffman encoding, top-K problems.

Priority Queue: A data structure that always gives you the highest-priority element first. A heap is the typical implementation.

PHP SPL:

SplMinHeap: Extract the minimum element.
SplMaxHeap: Extract the maximum element.
SplPriorityQueue: Priority queue where you specify the priority separately.
All implement SplHeap.

Array representation: A heap is typically stored as an array. For node at index i:

Left child: 2*i + 1
Right child: 2*i + 2
Parent: floor((i-1) / 2)

Top-K pattern: Find the K largest (or smallest) elements from N elements. Maintain a min-heap of size K. If new element > heap minimum, pop min and push new element. Final heap contains top K. O(n log k) — much better than O(n log n) sort.

Code Example

php

<?php
// SplMinHeap — always extracts the minimum
$minHeap = new \SplMinHeap();
$minHeap->insert(15);
$minHeap->insert(3);
$minHeap->insert(8);
$minHeap->insert(1);

echo $minHeap->extract(); // 1 (minimum)
echo $minHeap->extract(); // 3
echo $minHeap->top();     // 8 (peek without removal)

// SplMaxHeap — always extracts the maximum
$maxHeap = new \SplMaxHeap();
foreach ([5, 10, 2, 8, 1] as $val) { $maxHeap->insert($val); }
echo $maxHeap->extract(); // 10

// SplPriorityQueue — items with explicit priority (higher number = higher priority)
$taskQueue = new \SplPriorityQueue();
$taskQueue->setExtractFlags(\SplPriorityQueue::EXTR_BOTH); // get data AND priority
$taskQueue->insert(['action' => 'send_email'],   priority: 1);
$taskQueue->insert(['action' => 'process_payment'], priority: 10); // highest priority
$taskQueue->insert(['action' => 'update_cache'],  priority: 5);

while (!$taskQueue->isEmpty()) {
    $item = $taskQueue->extract();
    echo "{$item['data']['action']} (priority: {$item['priority']})\n";
}
// Output: process_payment (10), update_cache (5), send_email (1)

// Top-K elements — find K largest using a min-heap of size K
function topK(array $nums, int $k): array
{
    $heap = new \SplMinHeap();
    foreach ($nums as $num) {
        $heap->insert($num);
        if ($heap->count() > $k) {
            $heap->extract(); // remove the minimum — keep only K largest
        }
    }
    $result = [];
    while (!$heap->isEmpty()) { $result[] = $heap->extract(); }
    return array_reverse($result); // largest first
}

$top3 = topK([3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5], 3);
print_r($top3); // [9, 6, 5]

// Dijkstra's shortest path uses a min-heap (conceptual):
// - Store (distance, node) pairs
// - Always process the node with the smallest known distance next
// PHP implementation would use SplMinHeap with custom comparison

PreviousBinary trees and BSTs — traversal, searchData Structures in PHP NextGraphs — adjacency list, BFS, DFS in PHPData Structures in PHP