PHP Master | Datenstrukturen für PHP -Entwickler: Haufen

In diesem Artikel wird Haufen eingeführt, eine spezialisierte baumartige Datenstruktur, die eng mit Stapeln, Warteschlangen und Bäumen zusammenhängt. Heaps pflegen die Heap -Eigenschaft : Der Wert eines übergeordneten Knotens ist immer im Verhältnis zu den Werten seiner Kinder geordnet. Die Schlüsselkonzepte sind maximale Haken, Min-Häpten und vorrangige Warteschlangen.

Key Takeaways:

• Haufen sind baumähnliche Strukturen, die an der Haufen Eigenschaft haften. Variationen umfassen maximale Häpten (Eltern ≥ Kinder), Min-Häpten (Eltern ≤ Kinder) und vorrangige Warteschlangen.
• typischerweise als vollständige binäre Bäume implementiert, haben Haufen im Gegensatz zu binären Bäumen keine Geschwister- oder Cousin -Bestellung. Gemeinsame Operationen: Erstellen, Isempty, Einfügen, Extrakt.
• Array-basierte Heap-Implementierung ist machbar. Ein binärer Haufen mit n Knoten hat höchstens 2 n 1 -Knoten. Die Einfügung kehrt den Extraktionsprozess um.
• PHP bietet SplHeap, SplMaxHeap, SplMinHeap und SplPriorityQueue für die Haufen -Verwaltung. Prioritätswarteschlangen, häufig auf heap-basiert, verwenden Sie in Service-Schreibtischen und Graphalgorithmen.

Haufen im Detail:

max-heaps platzieren den größten Wert an der Wurzel, wobei Eltern immer größer oder gleich ihren Kindern sind. Min-Heaps sind die Umkehrung. PHPs SPS bietet Werkzeuge für all diese Typen. Ein max-heap-Beispiel:

Haufen, während oft binäre Bäume die inhärente Reihenfolge von binären Bäumen fehlen. Zu den grundlegenden Operationen gehören: Erstellen, Isempty, Einfügen und Extrakt (Entfernen der Wurzel). Extrahieren der Wurzel aus einem Haufen verlässt eine semiheap , die eine Umstrukturierung erfordert. Dies geschieht, indem der letzte Knoten auf die Wurzel verschoben und dann die neue Wurzel "rasen", bis die Haufen Eigenschaft wiederhergestellt ist.

Array-basierte Heap-Implementierung:

Ein binärer Max-heap kann mit einem Array implementiert werden. Der folgende PHP -Code zeigt dies:

<?php
class BinaryHeap {
    protected $heap;
    // ... (rest of the code as provided in the input) ...
}
?>

Insertion fügt dem Ende ein Element hinzu und "trinkt es" zu seiner richtigen Position ". Die Extraktion entfernt das Wurzel, ersetzt es durch das letzte Element und "trinkt es nach unten".

SplMaxHeap und SplMinHeap:

Phps SplMaxHeap und SplMinHeap vereinfachen Sie das Heap -Management. Erweitern Sie diese Klassen und überschreiben Sie die compare -Methode für benutzerdefinierte Vergleiche.

SplPriorityQueue:

SplPriorityQueue wirkt wie eine Warteschlange, verwendet aber intern einen Max-heap. Es ist nützlich für vorrangige Aufgaben. Überschreiben Sie die Methode compare, um die Prioritätsordnung zu definieren. Beispiel:

<?php
class PriQueue extends SplPriorityQueue {
    public function compare($p1, $p2) {
        // ... (comparator logic) ...
    }
}
?>

Zusammenfassung:

Dieser Artikel umfasste die Heap -Datenstruktur, seine Implementierung in PHP (sowohl manuell als auch mit SPL -Klassen) und seine Anwendungen, insbesondere in vorrangigen Warteschlangen. Zukünftige Artikel werden Diagramme untersuchen.

häufig gestellte Fragen (FAQ):

Der bereitgestellte FAQ -Abschnitt ist umfassend und befasst sich genau mit gemeinsamen Fragen zu Haufen in PHP. Es besteht keine Notwendigkeit einer Änderung oder Addition.

Das obige ist der detaillierte Inhalt vonPHP Master | Datenstrukturen für PHP -Entwickler: Haufen. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!