当前位置：首页 > PHP

php实现堆

2026-01-29 18:12:32PHP

堆的基本概念

堆是一种特殊的完全二叉树，分为最大堆和最小堆。最大堆的每个父节点值大于或等于其子节点值，最小堆则相反。堆常用于优先队列和堆排序算法。

PHP实现最大堆

以下代码展示如何用PHP实现最大堆的基本操作：

class MaxHeap {
    private $heap;

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

    private function parent($i) {
        return floor(($i - 1) / 2);
    }

    private function leftChild($i) {
        return 2 * $i + 1;
    }

    private function rightChild($i) {
        return 2 * $i + 2;
    }

    private function swap(&$x, &$y) {
        $temp = $x;
        $x = $y;
        $y = $temp;
    }

    public function insert($key) {
        array_push($this->heap, $key);
        $this->heapifyUp(count($this->heap) - 1);
    }

    private function heapifyUp($i) {
        while ($i > 0 && $this->heap[$this->parent($i)] < $this->heap[$i]) {
            $this->swap($this->heap[$i], $this->heap[$this->parent($i)]);
            $i = $this->parent($i);
        }
    }

    public function extractMax() {
        if (empty($this->heap)) {
            return null;
        }
        $max = $this->heap[0];
        $this->heap[0] = array_pop($this->heap);
        $this->heapifyDown(0);
        return $max;
    }

    private function heapifyDown($i) {
        $maxIndex = $i;
        $left = $this->leftChild($i);
        $right = $this->rightChild($i);
        $size = count($this->heap);

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

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

        if ($i != $maxIndex) {
            $this->swap($this->heap[$i], $this->heap[$maxIndex]);
            $this->heapifyDown($maxIndex);
        }
    }

    public function getMax() {
        return empty($this->heap) ? null : $this->heap[0];
    }

    public function size() {
        return count($this->heap);
    }
}

使用示例

$heap = new MaxHeap();
$heap->insert(3);
$heap->insert(9);
$heap->insert(2);
$heap->insert(1);
$heap->insert(7);

echo $heap->extractMax(); // 输出9
echo $heap->extractMax(); // 输出7

实现最小堆

将比较符号反转即可实现最小堆。修改heapifyUp和heapifyDown中的比较符号：

php实现堆

private function heapifyUp($i) {
    while ($i > 0 && $this->heap[$this->parent($i)] > $this->heap[$i]) {
        // 改为大于号
        $this->swap($this->heap[$i], $this->heap[$this->parent($i)]);
        $i = $this->parent($i);
    }
}

private function heapifyDown($i) {
    $minIndex = $i;
    // 改为小于号比较
    if ($left < $size && $this->heap[$left] < $this->heap[$minIndex]) {
        $minIndex = $left;
    }
    // 改为小于号比较
    if ($right < $size && $this->heap[$right] < $this->heap[$minIndex]) {
        $minIndex = $right;
    }
}