PHP の最小ヒープ アルゴリズムの原理と適用シナリオは何ですか?

PHP の最小ヒープ アルゴリズムの原理と適用シナリオは何ですか?

最小ヒープ (最小ヒープ) は、各ノードの値がその子ノードの値以下である特殊なバイナリ ツリー構造です。その主な原則は、ヒープのルート ノードが常に最小になるように特定の順序を維持することです。 PHP で配列を使用して最小ヒープを実装できます。

最小ヒープの原則は、挿入と削除という 2 つの基本操作を通じてその特性を維持することです。挿入操作では、新しい要素がヒープに追加され、その値のサイズに応じて調整され、ヒープの特性が破壊されないようにします。削除操作では、ヒープ内の最小の要素が削除され、最小ヒープの特性を満たすようにヒープのサイズが変更されます。

以下は、PHP を使用して最小ヒープ アルゴリズムを実装する方法を示すサンプル コードです:

class MinHeap {
    protected $heap;
    protected $size;
    
    public function __construct() {
        $this->heap = [];
        $this->size = 0;
    }
    
    public function insert($value) {
        $this->heap[$this->size] = $value;
        $this->size++;
        
        $this->heapifyUp($this->size - 1);
    }
    
    public function removeMin() {
        if ($this->isEmpty()) {
            return null;
        }
        
        $min = $this->heap[0];
        
        // 将最后一个元素移到根节点位置
        $this->heap[0] = $this->heap[$this->size - 1];
        
        $this->size--;
        
        // 调整堆，保持最小堆的特性
        $this->heapifyDown(0);
        
        return $min;
    }
    
    public function isEmpty() {
        return $this->size === 0;
    }
    
    protected function getParentIndex($index) {
        return ($index - 1) / 2;
    }
    
    protected function getLeftChildIndex($index) {
        return 2 * $index + 1;
    }
    
    protected function getRightChildIndex($index) {
        return 2 * $index + 2;
    }
    
    protected function heapifyUp($index) {
        $parentIndex = $this->getParentIndex($index);
        
        while ($index > 0 && $this->heap[$parentIndex] > $this->heap[$index]) {
            // 交换节点位置
            list($this->heap[$parentIndex], $this->heap[$index]) = [$this->heap[$index], $this->heap[$parentIndex]];
            
            $index = $parentIndex;
            $parentIndex = $this->getParentIndex($index);
        }
    }
    
    protected function heapifyDown($index) {
        $leftChildIndex = $this->getLeftChildIndex($index);
        $rightChildIndex = $this->getRightChildIndex($index);
        
        $minIndex = $index;
        
        if ($leftChildIndex < $this->size && $this->heap[$leftChildIndex] < $this->heap[$minIndex]) {
            $minIndex = $leftChildIndex;
        }
        
        if ($rightChildIndex < $this->size && $this->heap[$rightChildIndex] < $this->heap[$minIndex]) {
            $minIndex = $rightChildIndex;
        }
        
        if ($minIndex !== $index) {
            // 交换节点位置
            list($this->heap[$minIndex], $this->heap[$index]) = [$this->heap[$index], $this->heap[$minIndex]];
            
            $this->heapifyDown($minIndex);
        }
    }
}

// 使用最小堆进行排序
function heapSort($arr) {
    $heap = new MinHeap();
    foreach ($arr as $value) {
        $heap->insert($value);
    }
    
    $sorted = [];
    while (!$heap->isEmpty()) {
        $sorted[] = $heap->removeMin();
    }
    
    return $sorted;
}

// 测试用例
$arr = [5, 2, 9, 1, 7];
$sorted = heapSort($arr);
echo implode(', ', $sorted); // 输出：1, 2, 5, 7, 9

最小ヒープ アルゴリズムには多くのアプリケーション シナリオがあり、最も一般的なのは優先度です。列。優先キューは、要素が優先順位に基づいてデキューされる順序を決定できる特別なキューです。最小ヒープは優先キューを簡単に実装でき、挿入および削除操作の時間計算量は O(log n) であり、非常に効率的です。

プライオリティ キューに加えて、最小ヒープは次のシナリオにも適用できます:

1. セット内の最小または最大の要素の検索;
2. 最小スパニング ツリー アルゴリズム (Prim アルゴリズムなど)、
3. ヒープ ソート (上記のサンプル コードなど)、
4. ハフマン コーディング (ハフマン コーディング) など。

要約すると、PHP の最小ヒープ アルゴリズムは、多くの問題を解決する上で大きな役割を果たすことができる一般的に使用されるデータ構造です。優先キュー操作の実行、最小/最大要素の検索、または他のアルゴリズムでの使用のいずれの場合でも、min-heap は効率的なソリューションを提供できます。 min-heap の原理とコード実装を理解することで、このアルゴリズムをより適切に適用し、最適化することができます。

以上がPHP の最小ヒープ アルゴリズムの原理と適用シナリオは何ですか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。