⛰️ Heap - Priority-Based Structure

<?php
class MinHeap {
    private array $heap = [];

    // Insert - O(log n)
    public function insert(int $val): void {
        $this->heap[] = $val;
        $this->heapifyUp(count($this->heap) - 1);
    }

    private function heapifyUp(int $index): void {
        while ($index > 0) {
            $parent = intdiv($index - 1, 2);
            if ($this->heap[$parent] <= $this->heap[$index]) break;
            // Swap with parent
            [$this->heap[$parent], $this->heap[$index]] =
                [$this->heap[$index], $this->heap[$parent]];
            $index = $parent;
        }
    }

    // Extract Min - O(log n)
    public function extractMin(): ?int {
        if (empty($this->heap)) return null;
        $min = $this->heap[0];
        $last = array_pop($this->heap);
        if (!empty($this->heap)) {
            $this->heap[0] = $last;
            $this->heapifyDown(0);
        }
        return $min;
    }

    private function heapifyDown(int $index): void {
        $size = count($this->heap);
        while (true) {
            $smallest = $index;
            $left = 2 * $index + 1;
            $right = 2 * $index + 2;

            if ($left < $size && $this->heap[$left] < $this->heap[$smallest])
                $smallest = $left;
            if ($right < $size && $this->heap[$right] < $this->heap[$smallest])
                $smallest = $right;
            if ($smallest === $index) break;

            [$this->heap[$index], $this->heap[$smallest]] =
                [$this->heap[$smallest], $this->heap[$index]];
            $index = $smallest;
        }
    }

    // Peek - O(1)
    public function peek(): ?int {
        return $this->heap[0] ?? null;
    }

    public function size(): int { return count($this->heap); }
    public function isEmpty(): bool { return empty($this->heap); }
}

$heap = new MinHeap();
foreach ([5,3,8,1,9,2] as $v) $heap->insert($v);
while (!$heap->isEmpty()) {
    echo $heap->extractMin() . ' '; // 1 2 3 5 8 9 (sorted!)
}

// Heapify an array in-place (O(n) - Floyd's method)
function buildMinHeap(array &$arr): void {
    $n = count($arr);
    // Start from last non-leaf node
    for ($i = intdiv($n, 2) - 1; $i >= 0; $i--) {
        heapifyDownArray($arr, $n, $i);
    }
}

function heapifyDownArray(array &$arr, int $n, int $i): void {
    $smallest = $i; $left = 2*$i+1; $right = 2*$i+2;
    if ($left < $n && $arr[$left] < $arr[$smallest]) $smallest = $left;
    if ($right < $n && $arr[$right] < $arr[$smallest]) $smallest = $right;
    if ($smallest !== $i) {
        [$arr[$i], $arr[$smallest]] = [$arr[$smallest], $arr[$i]];
        heapifyDownArray($arr, $n, $smallest);
    }
}

// Heap Sort - O(n log n), O(1) space
function heapSort(array &$arr): void {
    $n = count($arr);
    buildMinHeap($arr);
    for ($i = $n - 1; $i > 0; $i--) {
        [$arr[0], $arr[$i]] = [$arr[$i], $arr[0]];
        heapifyDownArray($arr, $i, 0);
    }
    // Reverse for ascending order
    $arr = array_reverse($arr);
}

$heap = new SplMinHeap(); // or SplMaxHeap
$heap->insert(5); $heap->insert(3); $heap->insert(8);
foreach ($heap as $val) echo $val . ' '; // 3 5 8
echo $heap->top();  // 3 (minimum)
echo $heap->extract(); // 3 (removes it)