Untere Schranke für heapsort?

Also habe ich ein bisschen Graben mich und es sieht aus wie das Ergebnis eigentlich ziemlich neu! Die erste untere Schranke Beweis, den ich finden kann, ist von 1992, obwohl heapsort selbst erfunden wurde, in 1964.

Den formalen lower-bound-Nachweis ist aufgrund Schaffer und Sedgewick ist "Die Analyse von Heapsort" - Papier. Hier ist ein leicht umformuliert version des Beweises, die lässt einige der technischen details.

Beginnen, nehmen wir an, dass n = 2^k - 1 für gewisse k, die garantiert, dass wir eine vollständige Binär-heap. Ich werde zeigen, wie in diesem Fall behandeln später separat. Denn wir haben 2^k - 1 Elemente, in der ersten Phase von heapsort wird, in Θ(n) bauen Sie einen heap der Höhe k ist. Betrachten Sie nun die erste Hälfte des aus der Warteschlange entfernt von diesem Haufen, was entfernt 2^k-1 - Knoten aus dem heap. Die erste wichtige Beobachtung ist, dass, wenn Sie nehmen Sie die ab-heap und dann markiere alle Knoten hier, dass eigentlich am Ende immer aus der Warteschlange entfernt, Sie bilden eine Teilstruktur der heap (d.h. jeder Knoten, Holen Sie aus der Warteschlange entfernt ein Elternteil hat, bekommt auch aus der Warteschlange entfernt werden). Sie können dies sehen, da wenn dies nicht der Fall gewesen, dann hätte es einige Knoten, deren (groß) Eltern nicht bekommen, aus der Warteschlange entfernt werden, obwohl der Knoten selbst wurde aus der Warteschlange entfernt, was bedeutet, dass die Werte sind nicht in Ordnung.

Nun, überlegen Sie, wie die Knoten dieses Baumes sind verteilt über den Haufen. Wenn Sie die Beschriftung der Ebenen des Heaps, 0, 1, 2, ..., k - 1, dann gibt es eine gewisse Anzahl dieser Knoten in Ebenen 0, 1, 2, ..., k - 2 (also alles außer die Unterste Ebene der Struktur). Um für diese Knoten aus der Warteschlange entfernt bekommen aus dem Haufen, dann haben Sie ausgelagert, bis zu der Wurzel, und Sie werden nur getauscht, bis eine Ebene zu einer Zeit. Dies bedeutet, dass ein Weg, um die untere Schranke der Laufzeit von heapsort wäre, um die Anzahl der swaps, die erforderlich sind, um alle diese Werte bis zur Wurzel. In der Tat, das ist genau das, was wir tun werden.

Die erste Frage, die wir beantworten müssen, ist - wie viele der größten 2^k-1 - Knoten sind nicht in der untersten Ebene des heap? Wir können zeigen, dass dies nicht größer als 2^k-2 durch Widerspruch. Angenommen, es gibt mindestens 2^k-2 + 1 zu den größten Knoten in der untersten Ebene des heap. Die Eltern von diesen Knoten müssen auch große Knoten in der Ebene k - 2. Selbst im besten Fall, das heißt, es müssen mindestens 2^k-3 + 1 große Knoten in der Ebene k - 2, was dann bedeutet, dass es mindestens 2^k-4 + 1 große Knoten in der Ebene k - 3, usw. Aufsummiert über alle von diesen Knoten, die wir bekommen, es sind 2^k-2 + 2^k-3 + 2^k-4 + ... + 2⁰ + - k-große Knoten. Aber dieser Wert ist größer als 2^k-1im Widerspruch zu der Tatsache, dass wir die Arbeit mit nur 2^k-1 - Knoten hier.

Okay... wir wissen jetzt, dass es bei den meisten 2^k-2 großen Knoten in der unteren Schicht. Dies bedeutet, dass es müssen mindestens 2^k-2 der große Knoten in den ersten k-2 Schichten. Wir bitten nun - was ist die Summe, über alle von diesen Knoten, der Entfernung von diesem Knoten zur Wurzel? Gut, wenn wir 2^k-2 - Knoten positioniert, irgendwo in eine komplette Haufen, dann höchstens 2^k-3 von Ihnen kann in den ersten k - 3 Ebenen, und so gibt es zumindest 2^k-2 - 2^k-3 = 2^k-3 heavy-Knoten in der Ebene k - 2. Folglich ist die Gesamtzahl der swaps, die durchgeführt werden müssen, sind mindestens (k - 2) 2^k-3. Da n = 2^k-1, k = Θ(lg n), und so ist dieser Wert Θ(n lg n).

InformationsquelleAutor der Antwort templatetypedef

Hier ist eine Lösung, die verwendet CLRS Bedingungen:

Wir beginnen mit einem max-heap ist ein vollständiger binärer Baum mit n Elemente.

Wir können sagen, dass in einem vollständigen binären gibt es n/2 Blätter und n/2 innere Knoten.

n/2 Iterationen HEAP-SORT entfernen Sie die größten n/2 Elemente aus dem heap.

Lassen Sie S werden, der Satz von der größten n/2 Elemente.

Es kann bei den meisten n/4 Elemente aus S in die Blätter, da muss es zusätzliche n/4 von Ihnen in den inneren Knoten.

Lassen Sie L werden diese n/4 größten Elemente aus S sind in den Blättern.

Also, wenn es n/4 Elemente aus S auf Ebene 0 (die Blätter Ebene)
dann muss es mindestens n/8 von Ihnen auf Stufe 1.

Lassen Sie P werden diese n/8 Elemente aus S sind auf level 1.

n/2 Iterationen von HEAP-SORT kann die Elemente von L einen kurzen Schnitt auf die Wurzel
und dann aus dem heap, aber die Elemente von P müssen alle den Weg zur Wurzel, bevor Sie entfernt werden aus dem heap.

So gibt es zumindest (n/8)(lgn-1) Operationen,
das gibt uns eine Laufzeit von Ω(nlgn).

Nun für den Fall eines max-Heaps, der nicht alle seine Blätter auf Ebene 0.

Lassen Sie k werden die Anzahl der Blätter auf Ebene 0.

Nach k Iterationen von HEAP-SORT, wir sind Links mit einem max-heap ist
ein kompletter binärer Baum mit Höhe lgn-1.

Wir können weiterhin unser Beweis auf die gleiche Weise.

Nun für den Fall, wenn es weniger als n/4 Blätter von S.

Lassen Sie k werden die Anzahl der Elemente von S sind in den Blättern auf Ebene 0.

Wenn k <= n/8 dann muss es mindestens n/8 Elemente aus S auf Stufe 1.

Dies ist, weil es sein kann, insgesamt n/4 Elemente oberhalb der Stufe 1.

Wir sind weiterhin der Nachweis der gleichen Weise.

Wenn k>n/8 dann muss es mindestens n/16 Elemente aus S sind auf level 1.

Wir sind weiterhin der Nachweis der gleichen Weise.

Wir schließen, dass die Laufzeit von HEAP-SORT Ω(nlgn).

InformationsquelleAutor der Antwort Avi Cohen