PHP数据结构：堆数据结构的奥妙，实现高效的排序与优先级队列

PHP 中的堆数据结构是一种满足完全二叉树和堆性质（父结点值大于/小于子结点值）的树状结构，使用数组实现。堆支持两种操作：排序（从小到大提取最大元素）和优先级队列（根据优先级提取最大元素），分别通过 heapifyUp 和 heapifyDown 方法维护堆的性质。

PHP 中的堆数据结构：揭秘排序和优先级队列的奥秘

堆是一种树状数据结构，它满足以下两个性质：

• 完全二叉树性质：树中的每个结点都有两个子结点，或者没有子结点，形成一棵完全二叉树。
• 堆性质：每个父结点的值都大于（或等于）它的两个子结点的值（最大堆）或小于（或等于）它的两个子结点的值（最小堆）。

PHP 实现

在 PHP 中，我们使用数组来实现堆。以下是一个最大堆的 PHP 实现：

class MaxHeap {
    private $heap = array();
    private $size = 0;

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

    private function heapifyUp($index) {
        if ($index === 0) {
            return;
        }
        $parentIndex = intval(($index - 1) / 2);
        if ($this->heap[$index] > $this->heap[$parentIndex]) {
            $temp = $this->heap[$index];
            $this->heap[$index] = $this->heap[$parentIndex];
            $this->heap[$parentIndex] = $temp;
            $this->heapifyUp($parentIndex);
        }
    }

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

    private function heapifyDown($index) {
        $largestIndex = $index;
        $leftIndex = 2 * $index + 1;
        $rightIndex = 2 * $index + 2;
        if ($leftIndex < $this->size && $this->heap[$leftIndex] > $this->heap[$largestIndex]) {
            $largestIndex = $leftIndex;
        }
        if ($rightIndex < $this->size && $this->heap[$rightIndex] > $this->heap[$largestIndex]) {
            $largestIndex = $rightIndex;
        }
        if ($largestIndex !== $index) {
            $temp = $this->heap[$index];
            $this->heap[$index] = $this->heap[$largestIndex];
            $this->heap[$largestIndex] = $temp;
            $this->heapifyDown($largestIndex);
        }
    }
}

实战案例

排序：

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

while ($heap->size > 0) {
    echo $heap->extractMax() . " ";
}

输出：15 12 10 8 5

优先级队列：

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

while ($heap->size > 0) {
    $element = $heap->extractMax();
    echo "服务于元素 " . $element . "\n";
}

输出：
服务于元素 5
服务于元素 3
服务于元素 2
服务于元素 1

以上是PHP数据结构：堆数据结构的奥妙，实现高效的排序与优先级队列的详细内容。更多信息请关注PHP中文网其他相关文章！