当前位置：首页 > PHP

php堆实现

2026-02-14 11:16:01PHP

PHP 堆实现

在 PHP 中，堆（Heap）是一种特殊的树形数据结构，通常用于实现优先队列。堆可以分为最大堆和最小堆，最大堆的父节点值大于或等于子节点值，最小堆的父节点值小于或等于子节点值。

使用 SplHeap 类

PHP 提供了内置的 SplHeap 类来实现堆数据结构。SplHeap 是一个抽象类，需要继承并实现 compare 方法来定义堆的类型（最大堆或最小堆）。

class MaxHeap extends SplHeap {
    protected function compare($value1, $value2) {
        return $value1 - $value2;
    }
}

class MinHeap extends SplHeap {
    protected function compare($value1, $value2) {
        return $value2 - $value1;
    }
}

示例代码

以下是一个使用 MaxHeap 的示例：

$heap = new MaxHeap();
$heap->insert(10);
$heap->insert(5);
$heap->insert(15);

echo $heap->extract(); // 输出 15
echo $heap->extract(); // 输出 10
echo $heap->extract(); // 输出 5

手动实现堆

如果需要手动实现堆，可以使用数组来模拟堆结构。以下是一个最小堆的手动实现示例：

php堆实现

class MinHeapManual {
    private $heap = [];

    public function insert($value) {
        $this->heap[] = $value;
        $this->heapifyUp(count($this->heap) - 1);
    }

    public function extractMin() {
        if (count($this->heap) === 0) {
            return null;
        }
        $min = $this->heap[0];
        $last = array_pop($this->heap);
        if (count($this->heap) > 0) {
            $this->heap[0] = $last;
            $this->heapifyDown(0);
        }
        return $min;
    }

    private function heapifyUp($index) {
        $parent = floor(($index - 1) / 2);
        if ($index > 0 && $this->heap[$index] < $this->heap[$parent]) {
            $this->swap($index, $parent);
            $this->heapifyUp($parent);
        }
    }

    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;
    }
}

使用示例

$heap = new MinHeapManual();
$heap->insert(10);
$heap->insert(5);
$heap->insert(15);

echo $heap->extractMin(); // 输出 5
echo $heap->extractMin(); // 输出 10
echo $heap->extractMin(); // 输出 15