Untergrenze auf Haufen?

Question

Es ist bekannt, dass die Worst-Case-Laufzeit für Heapsort ω (n lg n) ist, aber ich habe Probleme, zu sehen, warum dies so ist. Insbesondere der erste Schritt von Heapsort (MAX-HEAP) braucht Zeit θ (n). Darauf folgen N -Heap -Löschungen. Ich verstehe, warum jede Heap -Löschung Zeit braucht O (LG n); Das Neuausgleich des Haufens beinhaltet eine blasende Operation, die Zeit o (h) in der Höhe des Haufens und H = O (LG N) braucht. Was ich jedoch nicht sehe, ist, warum dieser zweite Schritt ω (n lg n) dauern sollte. Es scheint, als würde ein einzelner Heap -Dequeue nicht unbedingt dazu führen, dass der Knoten nach oben bewegt wird, um den Baum ganz hinunter zu sprudeln.

Meine Frage ist: Kennt jemand einen guten Nachweis mit unterer gebundener Beweis für das Best-Case-Verhalten von Heapsort?

Answer 1

Also habe ich mich ein bisschen gegraben und es sieht so aus, als wäre dieses Ergebnis tatsächlich ziemlich neu! Der erste untergebundene Beweis, den ich finden kann, stammt aus dem Jahr 1992, obwohl die Haufen selbst 1964 erfunden wurde.

Der formelle Nachweis von unterer gebundener Beweis ist auf Schaffer und Sedgecs "The Analysis of Heapsort" -Papier zurückzuführen. Hier ist eine leicht umschriebene Version des Beweises, der einige der technischen Details auslässt.

Nehmen wir zunächst an, dass n = 2^k - 1 für einige k, was garantiert, dass wir einen vollständigen binären Haufen haben. Ich werde zeigen, wie ich diesen Fall später separat umgehen kann. Weil wir 2 haben^k - 1 Elemente, der erste Pass von Heapsort wird in θ (n) einen Haufen Höhe k aufbauen. Betrachten Sie nun die erste Hälfte der Dequeueues von diesem Haufen, der 2 entfernt^K-1 Knoten aus dem Haufen. Die erste wichtige Beobachtung ist, dass wenn Sie den Starthaufen nehmen und dann alle Knoten hier markieren, die tatsächlich dequed werden, sie einen Teilbaum des Haufens bilden (dh jeder Knoten, der dequed wird, hat einen Elternteil, der ebenfalls auf Dequeed wird). Sie können dies sehen, denn wenn dies nicht der Fall wäre, würde es einen Knoten geben, dessen (größere) Elternteils nicht gestaltet wurden, obwohl der Knoten selbst aufgehoben wurde, was bedeutet, dass die Werte nicht in Ordnung sind.

Überlegen Sie nun, wie die Knoten dieses Baumes über den Haufen verteilt sind. Wenn Sie die Ebenen des Haufens 0, 1, 2, ..., k - 1 beschriften, dann gibt es in den Stufen 0, 1, 2, ..., k - 2 einige dieser Knoten. alles außer der unteren Ebene des Baumes). Damit diese Knoten vom Haufen entleert werden können, müssen sie dann gegen die Wurzel ausgetauscht werden, und sie werden nur jeweils ein Level ausgetauscht. Dies bedeutet, dass ein Weg, um die Laufzeit von Heapsort zu untergraben, darin besteht, die Anzahl der Swaps zu zählen, die erforderlich sind, um alle diese Werte auf die Wurzel zu bringen. Genau das werden wir tun.

Die erste Frage, die wir beantworten müssen, ist - wie viele der größten 2^K-1 Knoten sind nicht in der unteren Ebene des Haufens? Wir können zeigen, dass dies nicht größer als 2 ist^K-2 im Widerspruch. Angenommen, es gibt mindestens 2^K-2 + 1 der größten Knoten in der unteren Ebene des Haufens. Dann muss jeder der Eltern dieser Knoten auch große Knoten in Stufe k - 2 sein. Auch im besten Fall bedeutet dies, dass es mindestens 2 geben muss^K-3 + 1 große Knoten in Stufe K - 2, was bedeutet, dass es mindestens 2 geben würde^K-4 + 1 große Knoten in Stufe K - 3 usw. Summieren über all diese Knoten, wir bekommen, dass es 2 gibt^K-2 + 2^K-3 + 2^K-4 + ... + 2⁰ + k große Knoten. Dieser Wert ist jedoch streng größer als 2^K-1, widersprechen der Tatsache, dass wir mit nur 2 arbeiten^K-1 Knoten hier.

Okay ... wir wissen jetzt, dass es höchstens 2 gibt^K-2 Große Knoten in der unteren Schicht. Dies bedeutet, dass es mindestens 2 geben muss^K-2 der großen Knoten in den ersten K-2-Schichten. Wir fragen nun: Was ist die Summe über all diese Knoten, von dem Abstand von diesem Knoten zur Wurzel? Nun, wenn wir 2 haben^K-2 Knoten, die irgendwo in einem vollständigen Haufen positioniert sind, dann höchstens 2^K-3 von ihnen können in den ersten K - 3 -Ebenen sein, und so gibt es mindestens 2^K-2 - 2^K-3 = 2^K-3 Schwere Knoten in Stufe K - 2. Folglich sind die Gesamtzahl der Swaps, die durchgeführt werden müssen, mindestens (k - 2) 2^K-3. Da n = 2^k-1, k = θ (lg n), und so ist dieser Wert θ (n lg n) nach Bedarf.

Answer 2

Einfache Beobachtungsantwort lautet: Die Elemente in Heap sind:

1
2
4
8
...
2^[log(n/4)]
and last level has between (1..2^[log(n/2)]) ==> (1,[n/2]) item, (by [] I mean Ceiling not roof)

Zum Beispiel, wenn Sie 7 Artikel haben:

1
2
4

Und wenn Sie 8 Artikel haben:

1
2
4
1

Es gibt 2 verschiedene Haufenbaum, zuerst mindestens N/4 - 1 Elemente eines Haufen n/4 - 1 Gegenstand im Level vor dem letzten, im ersten Fall dauert es O((n/4 - 1) * log(n/2)) Um die letztem Level -Elemente aus dem Haufen zu entfernen, und im zweiten Fall dauert es O((n/4 - 1) * log(n/4)) Elemente aus dem letzten Level entfernen. In beiden Fällen dauert es also ω (n log (n)) nur für N/4 - 1 -Elemente, sodass es eine untere Grenze ist (kann leicht sagen, dass es sich um eine enge Untergrenze handelt).

Answer 3

Hier ist eine Lösung, die CLRS -Begriffe verwendet:
Wir beginnen mit einem max-heap, der ein kompletter binärer Baum ist mit n Elemente.
Wir können sagen, dass es in einer vollständigen Binärdatei gibt n/2 Blätter und n/2 innere Knoten.
n/2 Iterationen von HEAP-SORT Entfernen Sie das größte n/2 Elemente aus dem Haufen.
Lassen S Sei der Set der größten n/2 Elemente.
Es kann höchstens geben n/4 Elemente von S in den Blättern, da es zusätzliche geben muss n/4 von ihnen in den inneren Knoten.
Lassen L seien diese n/4 größte Elemente von S das sind in den Blättern.
Also wenn es gibt n/4 Elemente von S Auf Stufe 0 (die Blätterstufe) muss es mindestens vorhanden sein n/8 von ihnen auf Stufe 1.
Lassen P seien diese n/8 Elemente von S das sind auf Stufe 1.
n/2 Iterationen von Heap-Sort können die Elemente aus geben L Ein kurzer Schnitt an der Wurzel und dann aus dem Haufen, aber die Elemente von P Muss bis zur Wurzel kommen, bevor sie vom Haufen entfernt werden.
Also gibt es zumindest (n/8)(lgn-1) Operationen, die uns eine Laufzeit von ω (NLGN) verleihen.
Jetzt für den Fall eines Max-HEAP, der nicht alle Blätter auf Stufe 0 hat.
Lassen k Seien Sie die Anzahl seiner Blätter auf Stufe 0.
Nach k Iterationen von Heap-Sort, wir haben einen Max-heap, der ein kompletter binärer Baum mit Höhe ist lgn-1.
Wir können unseren Beweis genauso fortsetzen.
Jetzt für den Fall, wenn es weniger als gibt n/4 Blätter von S.
Lassen k die Anzahl der Elemente sein S das sind in den Blättern auf Stufe 0.
Wenn k <= n/8 Dann muss es zumindest geben n/8 Elemente von S auf Stufe 1.
Dies liegt daran, dass es insgesamt insgesamt geben kann n/4 Elemente über Stufe 1.
Wir setzen den Beweis so fort.
Wenn k>n/8 Dann muss es zumindest geben n/16 Elemente von S das sind auf Stufe 1.
Wir setzen den Beweis so fort.
Wir schließen daraus, dass die Laufzeit von Heap-Sort ω (NLGN) ist.