siftUp und siftDown-operation bei heap für heapifying ein array
Davon ausgehen MAX-HEAPIFY operation. wo das Elternelement Wert größer ist, als sein Kind Werte.
siftDown swaps ein Knoten, der zu klein ist, mit Ihrem größten Kind (dabei bewegen Sie es nach unten), bis er mindestens so groß wie beide Knoten
unten es.siftUp-swaps ein Knoten, der zu groß ist mit seinen Eltern (und damit verschieben
es), bis es nicht größer ist, als die Knoten von oben zu. Die buildHeap
die Funktion nimmt ein array mit unsortierten Elemente und verschiebt Sie, bis er Sie
alle erfüllen die heap-Eigenschaft.
Gibt es zwei Ansätze, die könnte man nehmen für buildHeap. Einer ist zum starten
an der Spitze des Haufens (der Anfang des Arrays), und rufen Sie siftUp auf
jedes Element ist. Bei jedem Schritt werden die zuvor gesiebt items (Gegenstände vor
das aktuelle Element im array) bilden einen gültigen heap, und die nächste Sichtung
Element-up-Plätze in eine gültige position im heap. Nach Sichtung bis
jeder Knoten, alle Elemente erfüllen die heap-Eigenschaft. Der zweite Ansatz
geht in die entgegengesetzte Richtung: start am Ende des Arrays und move
rückwärts in Richtung der Vorderseite. Bei jeder iteration, die Sie sichten ein Element nach unten
bis es in der korrekten Position.
Lassen, die ein array hat 5 Elemente a[4,2,3,5,6] .
siftUp-
input - a[4,2,3,5,6]
Verarbeitung-
Anwendung siftUp opearation aus dem Beginn des Arrays.
siftUp(4)-
kein swap da ist die Wurzel
heapified Array-a[4]
siftUp(2)-
kein swap als übergeordneten Wert(4) ist mehr
heapified Array-a[4,2]
siftUp(3)-
kein swap als übergeordneten Wert(4) ist mehr
heapified Array-a[4,2,3]
siftUp(5)-
übergeordneten Wert ist 2, also wird swap (5,2).
Array-a[4,5,3,2]
nun 5 parent-Wert ist 4, also wieder einmal swap (5,4).
heapified Array-a[5,4,3,2]
siftUp(6)-
ersten swap zwischen (6,4), dann zwischen (6,5)
heapified Array-a[6,5,3,2,4]
Ausgabe-a[6,5,3,2,4]
siftDown-
input - a[4,2,3,5,6]
Verarbeitung-
Vom Ende des Arrays, die wir anwenden siftDown-operation eins nach dem anderen.
siftDown(6)-
Er hat kein Kind, also kein Tausch. Das gleiche gelte für siftDown(5) und siftDown(3) auch, wie Sie dont haben jedes Kind.Also Sie kann nicht weiter nach unten.
Array bis jetzt - der eine[4,2,3,5,6]
siftDown(2)-
Wird es getauscht mit dem größeren Kind Wert. Hier 6 die größere ist. also swap (2,6).
Nun Array wil -a[4,6,3,5,2]
siftDown(4)-
4 hat zwei-Kinder-6 und 3. swap mit den größeren. swap (4,6) durchgeführt.
Jetzt Array - a[6,4,3,5,2]
Wieder 4 muss getauscht werden, weil Sie ein Kind hat, die größer ist als Sie selbst, die ist 5 . also swap (4,5) erfolgt.
Array - a[6,5,3,4,2]
Heapified array a[6,5,3,4,2]
Ausgabe-a[6,5,3,4,2]
warum bekomme ich zwei verschiedene Ausgänge, wenn dabei siftUp und siftDown-operation auf derselben Menge von Elementen? Oder ist es möglich, unterschiedliche Haufen, wenn siftUp und siftDown angewendet, um die gleiche Menge von Elementen. Bitte klären Sie. 🙂
- Ihr Beispiel beweist, dass die resultierenden Haufen unterschiedlich sein kann. Beide sind gültig für die angegebenen Elemente. Die anderen, kleineren Beispiel, das ich denken kann, ist [1, 2, 3]
- Ja,das ist wahr.
Du musst angemeldet sein, um einen Kommentar abzugeben.
Ja, es ist möglich, verschiedene heaps für die gleiche Menge von Elementen.
Beide Ansätze korrekt produzieren Haufen Erfüllung der heap-Eigenschaft: das Elternelement Wert größer ist, als sein Kind Werte.
Den ersten Ansatz:
Den zweiten Ansatz:
In der Tat, wenn Sie ziehen Sie es von hand, es gibt auch andere mögliche haufenweise, z.B.
Beachten Sie jedoch, dass beide Ansätze, obwohl generieren korrekte Ergebnisse, Sie haben unterschiedliche Komplexitäten. Sehen Wie können Gebäude einen heap O(n) Zeitkomplexität?.
Die erste Methode, die Sie beschreiben (top-down) ist nicht die normale Vorgehensweise zum erstellen eines Heaps aus einem unsortierten array, wahrscheinlich, weil es dauern würde, O(n log n) Zeit !! Dies ist, weil es impliziert das ausführen sift-up-Vorgänge auf den unteren Ebenen (untere Ebene Größe n/2 und die Tiefe ist log n).
Dem normalen Ansatz ist ein bottom-up-Scannen des Arrays, und führen Sie einen sift-down für jeden Knoten. Die Zeit für jede Ebene die Anzahl der Knoten in der Ebene, multipliziert mit der Höhe (da sift-down ist recusrive und vielleicht tauschen alle den Weg zur untersten Ebene). Insgesamt wäre die Zeit O(1*n/2 + 2*n/4 + 3*n/8 + ...)=O(n)*(1/2 + 2/4 + 3/8 + ...)=O(n)*2=O(n).
`