Struktur data PHP: Rahsia struktur data timbunan, merealisasikan pengisihan dan barisan keutamaan yang cekap

Struktur data timbunan dalam PHP ialah struktur pepohon yang memenuhi ciri pokok binari dan timbunan yang lengkap (nilai nod induk lebih besar/kurang daripada nilai nod anak), dan dilaksanakan menggunakan tatasusunan. Timbunan menyokong dua operasi: pengisihan (mengekstrak elemen terbesar dari kecil ke besar) dan baris gilir keutamaan (mengekstrak elemen terbesar mengikut keutamaan Sifat timbunan dikekalkan melalui kaedah heapifyUp dan heapifyDown).

Timbunan struktur data dalam PHP: Mendedahkan rahsia pengisihan dan baris gilir keutamaan

Timbunan ialah struktur data seperti pepohon yang memenuhi dua sifat berikut:

• pokok binari lengkap Setiap nod dalam mempunyai dua nod anak atau tiada nod anak, membentuk pokok binari yang lengkap.
• Sifat timbunan: Nilai setiap nod induk adalah lebih besar daripada (atau sama dengan) nilai dua nod anaknya (timbunan maks) atau kurang daripada (atau sama dengan) nilai dua nod anaknya (timbunan min ).

Pelaksanaan PHP

Dalam PHP, kami menggunakan tatasusunan untuk melaksanakan timbunan. Berikut ialah pelaksanaan PHP bagi timbunan maksimum:

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);
        }
    }
}

Kes sebenar

Isih:

$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() . " ";
}

Output: 15 12 10 8 5

Isih:

$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";
}

Output: 15 12 10 8 5



:

Elemen sajian 5 🎜Layan elemen 3🎜Layan elemen 2🎜Layan elemen 1🎜

Atas ialah kandungan terperinci Struktur data PHP: Rahsia struktur data timbunan, merealisasikan pengisihan dan barisan keutamaan yang cekap. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!