[GO] Python Priority Queue Das Geheimnis des Ergebnisses der Heapify-Funktion, an dem die meisten Menschen nicht interessiert wären

Einführung

Ich habe den mysteriösen Teil des Verhaltens der Prioritätswarteschlange in Python untersucht.

Geheimnisvolles Verhalten

Hier , als ich die Prioritätswarteschlange in Python überprüfte, war es möglich, sie mit der Heapq-Bibliothek zu realisieren. .. Im obigen Link wird das Folgende als Beispiel für die Verwendung von heapq beschrieben.

#Quelle: https://qiita.com/ell/items/fe52a9eb9499b7060ed6
import heapq  #Import der Heapq-Bibliothek

a = [1, 6, 8, 0, -1]
heapq.heapify(a)  #Liste zur Prioritätswarteschlange
print(a)
#Ausgabe: [-1, 0, 8, 1, 6](Prioritätswarteschlange a)

Warum erfolgt die Ausgabe in dieser Reihenfolge ([-1, 0, 8, 1, 6])? Es stellte sich eine Frage, an der niemand interessiert zu sein schien (weil ich aufsteigende Reihenfolge erwartete).

Grund: Weil die Elemente der Liste nach dem Heap-Warteschlangenalgorithmus sortiert sind

In Python scheinen Prioritätswarteschlangen durch eine Liste dargestellt zu werden. Gemäß dem Python-Dokument wird der Inhalt der Liste nach dem Heap-Warteschlangenalgorithmus sortiert. Ding.

Hier Auf der Heap-Erklärungsseite finden Sie eine detaillierte Erklärung des Heap-Algorithmus. , Die Baumstruktur kann durch eine Liste dargestellt werden (vorausgesetzt, der Listenindex des übergeordneten Knotens ist i, der linke Knoten des untergeordneten Knotens ist 2 * i und der rechte Knoten ist 2 * i + 1). Die obige Ausgabe wurde erhalten, indem die Elemente in der Liste ausgetauscht wurden, sodass die Eltern-Kind-Beziehung hergestellt wurde.

Sortieren Sie den Fluss nach dem Heap-Warteschlangenalgorithmus

• Siehe hier für den detaillierten Algorithmus.

Heap-Bedingung: Jeder Knoten ist kleiner oder gleich seinen untergeordneten Knoten Anfangssequenz: [1, 6, 8, 0, -1]