Apakah prinsip dan senario aplikasi algoritma timbunan minimum dalam PHP?

Apakah prinsip dan senario aplikasi algoritma timbunan minimum dalam PHP?

Timbunan Min (Timbunan Min) ialah struktur pokok binari khas di mana nilai setiap nod adalah kurang daripada atau sama dengan nilai nod anaknya. Prinsip utamanya adalah untuk mengekalkan susunan tertentu supaya nod akar timbunan sentiasa terkecil. Tatasusunan boleh digunakan dalam PHP untuk melaksanakan timbunan min.

Prinsip min-heap adalah untuk mengekalkan ciri-cirinya melalui dua operasi asas: sisipan dan pemadaman. Operasi sisipan menambah elemen baharu pada timbunan dan melaraskannya dengan sewajarnya mengikut saiz nilainya, memastikan ciri timbunan tidak dimusnahkan. Operasi padam memadamkan elemen terkecil dalam timbunan dan mengubah saiz timbunan supaya ia masih memenuhi ciri timbunan min.

Berikut ialah contoh kod yang menunjukkan cara menggunakan PHP untuk melaksanakan algoritma timbunan minimum:

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

Algoritma timbunan minimum mempunyai banyak senario aplikasi, yang paling biasa ialah Gilir Keutamaan. Baris gilir keutamaan ialah baris gilir khas yang boleh menentukan susunan unsur-unsur disingkirkan berdasarkan keutamaannya. Timbunan minimum boleh dengan mudah melaksanakan baris gilir keutamaan, dan kerumitan masa operasi sisipan dan pemadaman ialah O(log n), yang sangat cekap.

Selain barisan keutamaan, timbunan min juga boleh digunakan pada senario berikut:

1. Mencari elemen terkecil atau terbesar dalam satu set
2. Algoritma pokok rentang minimum (seperti algoritma Prim.); (seperti kod contoh di atas) ;
3. Pengkodan Huffman, dsb.
4. Ringkasnya, algoritma timbunan minimum dalam PHP ialah struktur data yang biasa digunakan yang boleh memainkan peranan besar dalam menyelesaikan banyak masalah. Sama ada menjalankan operasi baris gilir keutamaan, mencari elemen minimum/maksimum atau digunakan dalam algoritma lain, timbunan min boleh memberikan penyelesaian yang cekap. Dengan memahami prinsip dan pelaksanaan kod min-heap, algoritma ini boleh digunakan dengan lebih baik dan dioptimumkan.

Atas ialah kandungan terperinci Apakah prinsip dan senario aplikasi algoritma timbunan minimum dalam PHP?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!