当前位置：首页 > PHP

php堆实现

2026-02-28 10:26:02PHP

PHP 堆（Heap）实现方法

堆是一种特殊的树形数据结构，通常用于实现优先队列。PHP 提供了内置的 SplHeap 类，同时也支持通过数组手动实现堆。

php堆实现

使用 `SplHeap` 类

PHP 的 SPL（Standard PHP Library）提供了 SplHeap 抽象类，可以快速实现最大堆或最小堆。

// 最小堆实现
class MinHeap extends SplHeap {
    protected function compare($value1, $value2) {
        return $value2 - $value1;
    }
}

// 最大堆实现
class MaxHeap extends SplHeap {
    protected function compare($value1, $value2) {
        return $value1 - $value2;
    }
}

// 示例用法
$minHeap = new MinHeap();
$minHeap->insert(3);
$minHeap->insert(1);
$minHeap->insert(4);
echo $minHeap->extract(); // 输出 1

手动实现堆（基于数组）

如果需要更灵活的堆实现，可以通过数组手动构建：

class BinaryHeap {
    private $heap;

    public function __construct() {
        $this->heap = [];
    }

    // 插入元素并调整堆
    public function insert($item) {
        $this->heap[] = $item;
        $this->heapifyUp(count($this->heap) - 1);
    }

    // 提取堆顶元素
    public function extract() {
        if (count($this->heap) === 0) {
            return null;
        }

        $root = $this->heap[0];
        $last = array_pop($this->heap);

        if (count($this->heap) > 0) {
            $this->heap[0] = $last;
            $this->heapifyDown(0);
        }

        return $root;
    }

    // 向上调整（用于插入）
    private function heapifyUp($index) {
        $parent = ($index - 1) >> 1;

        while ($index > 0 && $this->heap[$parent] > $this->heap[$index]) {
            $this->swap($parent, $index);
            $index = $parent;
            $parent = ($index - 1) >> 1;
        }
    }

    // 向下调整（用于提取）
    private function heapifyDown($index) {
        $left = 2 * $index + 1;
        $right = 2 * $index + 2;
        $smallest = $index;

        if ($left < count($this->heap) && $this->heap[$left] < $this->heap[$smallest]) {
            $smallest = $left;
        }

        if ($right < count($this->heap) && $this->heap[$right] < $this->heap[$smallest]) {
            $smallest = $right;
        }

        if ($smallest !== $index) {
            $this->swap($index, $smallest);
            $this->heapifyDown($smallest);
        }
    }

    // 交换元素
    private function swap($i, $j) {
        $temp = $this->heap[$i];
        $this->heap[$i] = $this->heap[$j];
        $this->heap[$j] = $temp;
    }
}