Struktur data PHP: Rahsia struktur data timbunan, merealisasikan pengisihan dan barisan keutamaan yang cekap-tutorial php-php.cn

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

WBOY

Lepaskan： 2024-06-01 15:54:01

asal

1197 orang telah melayarinya

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).

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

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

Salin selepas log masuk

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

Salin selepas log masuk

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

Salin selepas log masuk

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!