PHP-Datenstruktur: Das Geheimnis der Heap-Datenstruktur, die effiziente Sortierung und Prioritätswarteschlange realisiert

Die Heap-Datenstruktur in PHP ist eine Baumstruktur, die die vollständigen Binärbaum- und Heap-Eigenschaften erfüllt (der Wert des übergeordneten Knotens ist größer/kleiner als der Wert des untergeordneten Knotens) und mithilfe eines Arrays implementiert wird. Der Heap unterstützt zwei Vorgänge: Sortieren (Extrahieren des größten Elements von klein nach groß) und Prioritätswarteschlange (Extrahieren des größten Elements nach Priorität). Die Eigenschaften des Heaps werden über die Methoden heapifyUp bzw. heapifyDown verwaltet.

Heap-Datenstruktur in PHP: Enthüllung der Geheimnisse der Sortierung und Prioritätswarteschlangen

Der Heap ist eine baumartige Datenstruktur, die die folgenden zwei Eigenschaften erfüllt:

• Vollständiger Binärbaum Eigenschaft: Baum Jeder Knoten hat zwei oder keine untergeordneten Knoten und bildet einen vollständigen Binärbaum.
• Heap-Eigenschaften: Der Wert jedes übergeordneten Knotens ist größer (oder gleich) dem Wert seiner beiden untergeordneten Knoten (maximaler Heap) oder kleiner (oder gleich) dem Wert seiner beiden untergeordneten Knoten (minimaler Heap). ).

PHP-Implementierung

In PHP verwenden wir Arrays, um Heap zu implementieren. Das Folgende ist eine PHP-Implementierung eines Max-Heaps:

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

Eigentlicher Fall

Sortierung:

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

Ausgabe: 15 12 10 8 5

Prioritätswarteschlange:

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

Ausgabe:
Servierelement 5
Element 3 servieren
Element 2 servieren
Element 1 servieren

Das obige ist der detaillierte Inhalt vonPHP-Datenstruktur: Das Geheimnis der Heap-Datenstruktur, die effiziente Sortierung und Prioritätswarteschlange realisiert. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!