PHPデータ構造：効率的なソートと優先キューを実現するヒープデータ構造の秘密

PHP のヒープ データ構造は、完全なバイナリ ツリーとヒープ プロパティ (親ノードの値が子ノードの値より大きい/小さい) を満たすツリー構造であり、配列を使用して実装されます。ヒープは、ソート (小さい要素から大きい要素への最大の要素の抽出) と優先キュー (優先順位に従って最大の要素の抽出) の 2 つの操作をサポートします。ヒープのプロパティは、それぞれ heapifyUp メソッドと heapifyDown メソッドによって維持されます。

PHP のヒープ データ構造: ソートと優先キューの秘密を明らかにする

ヒープは、次の 2 つのプロパティを満たすツリー状のデータ構造です:

• 完全なバイナリ ツリー プロパティ: treeの各ノードには 2 つの子ノードがあるか、子ノードがなく、完全なバイナリ ツリーを形成します。
• ヒーププロパティ: 各親ノードの値が、その2つの子ノードの値(最大ヒープ)より大きい(または等しい)か、その2つの子ノードの値(最小ヒープ)より小さい(または等しい)。 ）。

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 中国語 Web サイトの他の関連記事を参照してください。