php实现堆

PHP 实现堆数据结构

堆（Heap）是一种特殊的完全二叉树，分为最大堆和最小堆。最大堆的每个父节点值大于或等于子节点值，最小堆则相反。PHP 可以通过数组模拟堆结构，以下是实现方法。

最大堆的实现

class MaxHeap {
    private $heap;

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

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

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

    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;
        $largest = $index;

        if ($left < count($this->heap) && $this->heap[$left] > $this->heap[$largest]) {
            $largest = $left;
        }
        if ($right < count($this->heap) && $this->heap[$right] > $this->heap[$largest]) {
            $largest = $right;
        }
        if ($largest !== $index) {
            $this->swap($index, $largest);
            $this->heapifyDown($largest);
        }
    }

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

最小堆的实现

class MinHeap {
    private $heap;

    public function __construct() {
        $this->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;
    }
}

堆的应用示例

堆常用于优先级队列、堆排序等场景。以下是使用最大堆进行堆排序的示例：

function heapSort($array) {
    $heap = new MaxHeap();
    foreach ($array as $value) {
        $heap->insert($value);
    }
    $sorted = [];
    while ($max = $heap->extractMax()) {
        array_unshift($sorted, $max);
    }
    return $sorted;
}

$unsorted = [3, 7, 2, 9, 1, 5];
$sorted = heapSort($unsorted);
print_r($sorted); // 输出: [1, 2, 3, 5, 7, 9]

性能分析

堆的插入和删除操作的时间复杂度为 O(log n)，堆排序的时间复杂度为 O(n log n)。空间复杂度为 O(n)，因为需要存储堆结构。

通过上述实现，可以在 PHP 中高效地使用堆数据结构解决相关问题。