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中文網其他相關文章！