Wie kann der Aufbau eines Heaps eine Zeitkomplexität von O(n) haben?

Question

Kann mir jemand erklären, wie man einen Haufen bauen kann O(n) Komplexität?

Das Einfügen eines Elements in einen Heap ist O(log n) und die Einfügung wird n/2 Mal wiederholt (der Rest sind Blätter, die die Heap-Eigenschaft nicht verletzen können). Dies bedeutet also, dass die Komplexität wie folgt sein sollte O(n log n) würde ich denken.

Mit anderen Worten, für jedes Element, das wir "heapify", hat es das Potenzial, zu filtern (dh, zu sichten) einmal für jede Ebene für den Haufen so weit (das ist log n Ebenen).

Was übersehe ich?

Answer 1

Ich denke, dass in diesem Thema mehrere Fragen verborgen sind:

• Wie implementieren Sie buildHeap so läuft es in O(n) Zeit?
• Wie können Sie zeigen, dass buildHeap läuft ein O(n) Zeit, wenn sie richtig umgesetzt wird?
• Warum funktioniert dieselbe Logik nicht, um Heap Sort in O(n) Zeit statt O(n log n) ?

Wie implementieren Sie buildHeap so läuft es in O(n) Zeit?

Häufig konzentrieren sich die Antworten auf diese Fragen auf den Unterschied zwischen siftUp et siftDown . Die richtige Wahl treffen zwischen siftUp et siftDown ist entscheidend für den Erhalt O(n) Leistung für buildHeap aber es hilft nicht, den Unterschied zu verstehen zwischen buildHeap et heapSort im Allgemeinen. In der Tat sind ordnungsgemäße Implementierungen von sowohl buildHeap et heapSort wird nur verwenden. siftDown . En siftUp Operation wird nur benötigt, um Einfügungen in einen bestehenden Heap vorzunehmen, so dass sie z. B. zur Implementierung einer Prioritätswarteschlange mit einem binären Heap verwendet werden könnte.

Ich habe dies geschrieben, um zu beschreiben, wie ein Max Heap funktioniert. Diese Art von Heap wird typischerweise für Heap-Sortierung oder für eine Prioritätswarteschlange verwendet, bei der höhere Werte eine höhere Priorität angeben. Ein Min-Heap ist ebenfalls nützlich, z. B. beim Abrufen von Elementen mit ganzzahligen Schlüsseln in aufsteigender Reihenfolge oder von Zeichenketten in alphabetischer Reihenfolge. Die Prinzipien sind genau die gleichen; man muss nur die Sortierreihenfolge ändern.

En Haufeneigenschaft legt fest, dass jeder Knoten in einem binären Heap mindestens so groß sein muss wie seine beiden Kinder. Dies bedeutet insbesondere, dass sich das größte Element im Heap an der Wurzel befindet. Sifting down und Sifting up sind im Wesentlichen derselbe Vorgang in entgegengesetzter Richtung: Verschieben eines angreifenden Knotens, bis er die Heap-Eigenschaft erfüllt:

• siftDown tauscht einen zu kleinen Knoten mit seinem größten Unterknoten aus (und verschiebt ihn damit nach unten), bis er mindestens so groß ist wie die beiden darunter liegenden Knoten.
• siftUp tauscht einen zu großen Knoten mit seinem Elternteil aus (und verschiebt ihn dadurch nach oben), bis er nicht mehr größer ist als der darüber liegende Knoten.

Die Anzahl der Vorgänge, die für siftDown et siftUp ist proportional zu der Entfernung, die der Knoten möglicherweise zurücklegen muss. Für siftDown ist die Entfernung zum unteren Ende des Baumes, also siftDown ist für Knoten an der Spitze des Baums teuer. Mit siftUp ist die Arbeit proportional zum Abstand zur Spitze des Baumes, also siftUp ist für Knoten am unteren Ende des Baums teuer. Obwohl beide Operationen O(log n) Im schlimmsten Fall befindet sich in einem Haufen nur ein Knoten an der Spitze, während die Hälfte der Knoten in der unteren Schicht liegt. Also sollte es nicht allzu überraschend sein, dass wir, wenn wir eine Operation auf jeden Knoten anwenden müssen, die siftDown über siftUp .

En buildHeap Funktion nimmt ein Array unsortierter Elemente und verschiebt sie, bis sie alle die Heap-Eigenschaft erfüllen, wodurch ein gültiger Heap entsteht. Es gibt zwei Ansätze, die man für buildHeap unter Verwendung der siftUp et siftDown Operationen, die wir beschrieben haben.

1. Beginnen Sie am oberen Ende des Heaps (dem Anfang des Arrays) und rufen Sie siftUp für jeden Artikel. Bei jedem Schritt bilden die zuvor gesiebten Elemente (die Elemente vor dem aktuellen Element im Array) einen gültigen Haufen, und das Sieben des nächsthöheren Elements platziert dieses an einer gültigen Position im Haufen. Nach der Sichtung jedes Knotens erfüllen alle Elemente die Eigenschaft des Haufens.

2. Oder gehen Sie in die entgegengesetzte Richtung: Beginnen Sie am Ende des Feldes und bewegen Sie sich rückwärts nach vorne. Bei jeder Iteration sortieren Sie ein Element nach unten, bis es sich an der richtigen Stelle befindet.

Welche Implementierung für buildHeap effizienter ist?

Beide Lösungen ergeben einen gültigen Heap. Es überrascht nicht, dass die effizientere Lösung die zweite Operation ist, bei der siftDown .

Sea h = log n stellen die Höhe des Haufens dar. Der Arbeitsaufwand für die siftDown Ansatz ist gegeben durch die Summe

(0 * n/2) + (1 * n/4) + (2 * n/8) + ... + (h * 1).

Jeder Term in der Summe hat die maximale Entfernung, die ein Knoten in der gegebenen Höhe zurücklegen muss (Null für die unterste Schicht, h für die Wurzel), multipliziert mit der Anzahl der Knoten in dieser Höhe. Im Gegensatz dazu ist die Summe für den Aufruf von siftUp auf jedem Knoten ist

(h * n/2) + ((h-1) * n/4) + ((h-2)*n/8) + ... + (0 * 1).

Es sollte klar sein, dass die zweite Summe größer ist. Der erste Term allein ist hn/2 = 1/2 n log n Dieser Ansatz ist also bestenfalls komplex. O(n log n) .

Wie lässt sich die Summe für die siftDown Ansatz ist in der Tat O(n) ?

Eine Methode (es gibt auch andere Analysen, die funktionieren) besteht darin, die endliche Summe in eine unendliche Reihe umzuwandeln und dann Taylorreihen zu verwenden. Wir können den ersten Term ignorieren, der Null ist:

Wenn Sie sich nicht sicher sind, warum jeder dieser Schritte funktioniert, finden Sie hier eine Begründung für den Prozess in Worten:

• Die Terme sind alle positiv, so dass die endliche Summe kleiner sein muss als die unendliche Summe.
• Die Reihe ist gleich einer Potenzreihe, die bei x=1/2 .
• Diese Potenzreihe ist gleich (eine Konstante mal) der Ableitung der Taylor-Reihe für f(x)=1/(1-x) .
• x=1/2 innerhalb des Konvergenzintervalls dieser Taylor-Reihe liegt.
• Daher können wir die Taylor-Reihe ersetzen durch 1/(1-x) , differenzieren und auswerten, um den Wert der unendlichen Reihe zu finden.

Da die unendliche Summe genau n schließen wir, dass die endliche Summe nicht größer ist, und ist daher, O(n) .

Warum erfordert die Heap-Sortierung O(n log n) Zeit?

Wenn es möglich ist, die buildHeap in linearer Zeit, warum erfordert die Haufensortierung O(n log n) Zeit? Nun, die Haufensortierung besteht aus zwei Schritten. Erstens, wir rufen buildHeap auf dem Array, was eine O(n) Zeit, wenn sie optimal umgesetzt wird. Der nächste Schritt besteht darin, das größte Element im Heap wiederholt zu löschen und es an das Ende des Arrays zu setzen. Da wir ein Element aus dem Heap löschen, gibt es immer einen freien Platz direkt hinter dem Ende des Heaps, wo wir das Element speichern können. Die Haufensortierung erreicht also eine sortierte Reihenfolge, indem sie nacheinander das nächstgrößere Element entfernt und in das Array einfügt, wobei sie an der letzten Position beginnt und sich nach vorne bewegt. Es ist die Komplexität dieses letzten Teils, die bei Heap-Sortierung dominiert. Die Schleife sieht wie folgt aus:

for (i = n - 1; i > 0; i--) {
    arr[i] = deleteMax();
}

Offensichtlich läuft die Schleife O(n) mal ( n - 1 um genau zu sein, ist der letzte Punkt bereits vorhanden). Die Komplexität der deleteMax für einen Heap ist O(log n) . In der Regel wird die Wurzel (das größte Element im Heap) entfernt und durch das letzte Element im Heap ersetzt, das ein Blatt und damit eines der kleinsten Elemente ist. Diese neue Wurzel wird mit ziemlicher Sicherheit die Heap-Eigenschaft verletzen, daher müssen Sie siftDown bis Sie ihn wieder in eine akzeptable Position bringen. Dies hat auch zur Folge, dass das nächstgrößere Element an die Wurzel verschoben wird. Beachten Sie, dass im Gegensatz zu buildHeap wobei wir für die meisten Knotenpunkte siftDown vom unteren Ende des Baumes aus, rufen wir nun siftDown von der Spitze des Baumes bei jeder Iteration! Obwohl der Baum schrumpft, schrumpft er nicht schnell genug : Die Höhe des Baumes bleibt konstant, bis Sie die erste Hälfte der Knoten entfernt haben (wenn Sie die unterste Schicht vollständig entfernt haben). Für das nächste Viertel ist die Höhe dann h - 1 . Die Gesamtarbeit für diese zweite Stufe beträgt also

h*n/2 + (h-1)*n/4 + ... + 0 * 1.

Beachten Sie den Wechsel: Der Null-Arbeitsfall entspricht jetzt einem einzelnen Knoten und die h Der Arbeitsfall entspricht der Hälfte der Knotenpunkte. Diese Summe ist O(n log n) genau wie die ineffiziente Version von buildHeap die mit siftUp implementiert wird. Aber in diesem Fall haben wir keine Wahl, da wir versuchen, zu sortieren und wir verlangen, dass das nächstgrößere Element als nächstes entfernt wird.

Zusammenfassend lässt sich sagen, dass die Arbeit für die Haufensortierung die Summe der beiden Stufen ist: O(n) Zeit für buildHeap und O(n log n), um jeden Knoten der Reihe nach zu entfernen Die Komplexität ist also O(n log n) . Sie können (mit Hilfe einiger Ideen aus der Informationstheorie) beweisen, dass für eine vergleichsbasierte Sortierung, O(n log n) ist ohnehin das Beste, was man sich erhoffen kann. Es gibt also keinen Grund, davon enttäuscht zu sein oder zu erwarten, dass Heap Sort die O(n)-Zeitgrenze erreicht, die buildHeap tut.

Answer 2

Ihre Analyse ist richtig. Allerdings ist sie nicht dicht.

Es ist nicht ganz einfach zu erklären, warum der Aufbau eines Heaps eine lineare Operation ist, Sie sollten es besser lesen.

A hervorragende Analyse des Algorithmus ist zu sehen aquí .

---

Der Grundgedanke ist, dass in der build_heap Algorithmus den eigentlichen heapify Kosten sind nicht O(log n) für alle Elemente.

En heapify aufgerufen wird, hängt die Laufzeit davon ab, wie weit ein Element im Baum nach unten wandern kann, bevor der Prozess abgebrochen wird. Mit anderen Worten, sie hängt von der Höhe des Elements im Heap ab. Im schlimmsten Fall kann das Element bis auf die Blattebene hinabsteigen.

Zählen wir die geleistete Arbeit Ebene für Ebene.

Auf der untersten Ebene befinden sich 2^(h) Knoten, aber wir rufen nicht heapify auf einer dieser Ebenen, also ist die Arbeit 0. Auf der nächsten Ebene gibt es 2^(h 1) Knoten, und jeder kann sich um 1 Stufe nach unten bewegen. Auf der 3. Ebene von unten befinden sich 2^(h 2) Knoten, und jeder kann sich um 2 Ebenen nach unten bewegen.

Wie Sie sehen können, sind nicht alle Heapify-Operationen O(log n) Deshalb erhalten Sie O(n) .

Answer 3

Intuitiv:

"Die Komplexität sollte O(nLog n) sein... für jedes Element, das wir "heapify", hat es das Potenzial, einmal für jede Ebene für den Heap so weit nach unten zu filtern (was log n Ebenen ist)."

Nicht ganz. Ihre Logik führt nicht zu einer engen Schranke - sie überschätzt die Komplexität jedes Heapify. Wenn es von unten nach oben aufgebaut wird, kann die Einfügung (Heapify) viel weniger sein als O(log(n)) . Das Verfahren läuft wie folgt ab:

( Schritt 1 ) Die erste n/2 Elemente kommen in die unterste Reihe des Haufens. h=0 daher ist heapify nicht erforderlich.

( Schritt 2 ) Die nächste n/22 Die Elemente werden in der Reihe 1 von unten nach oben angeordnet. h=1 heapify filtert 1 Ebene tiefer.

( Schritt i ) Die nächste n/2i Elemente gehen in Reihe i von unten nach oben. h=i Heapify-Filter i Ebenen nach unten.

( Schritt log(n) ) Die letzte n/2log2(n) = 1 Element geht in Zeile log(n) von unten nach oben. h=log(n) Heapify-Filter log(n) Ebenen nach unten.

HINWEIS: das nach dem ersten Schritt, 1/2 der Elemente (n/2) befinden sich bereits im Heap, und wir mussten heapify nicht ein einziges Mal aufrufen. Beachten Sie auch, dass nur ein einziges Element, die Wurzel, tatsächlich die volle log(n) Komplexität.

---

Theoretisch:

Die Schritte insgesamt N um einen Haufen der Größe n kann mathematisch ausgedrückt werden.

In der Höhe i haben wir (oben) gezeigt, dass es n/2i+1 Elemente, die heapify aufrufen müssen, und wir wissen, dass heapify in Höhe i est O(i) . Dies ergibt:

Die Lösung der letzten Summation kann durch Ableitung der beiden Seiten der bekannten geometrischen Reihengleichung gefunden werden:

Schließlich wird durch das Einstecken von x = 1/2 in die obige Gleichung einsetzt, ergibt sich 2 . Setzt man dies in die erste Gleichung ein, erhält man:

Die Gesamtzahl der Schritte ist also groß O(n)

Answer 4

Es gibt bereits einige gute Antworten, aber ich möchte eine kleine visuelle Erklärung hinzufügen

Schauen Sie sich das Bild an, es gibt
n/2^1 grüne Knoten avec Höhe 0 (hier 23/2 = 12)
n/2^2 rote Knotenpunkte avec Höhe 1 (hier 23/4 = 6)
n/2^3 blauer Knoten avec Höhe 2 (hier 23/8 = 3)
n/2^4 violette Knoten avec Höhe 3 (hier 23/16 = 2)
Es gibt also n/2^(h+1) Knoten für Höhe h
Um die Zeitkomplexität zu ermitteln, zählen wir die Umfang der geleisteten Arbeit o maximale Anzahl der durchgeführten Iterationen durch jeden Knoten
Es ist nun festzustellen, dass jeder Knoten (höchstens) Folgendes leisten kann Iterationen == Höhe des Knotens

Green  = n/2^1 * 0 (no iterations since no children)  
red    = n/2^2 * 1 (heapify will perform atmost one swap for each red node)  
blue   = n/2^3 * 2 (heapify will perform atmost two swaps for each blue node)  
purple = n/2^4 * 3 (heapify will perform atmost three swaps for each purple node)   

also für jede Knoten mit der Höhe h Die maximal geleistete Arbeit beträgt n/2^(h+1) * h

Die gesamte geleistete Arbeit beträgt nun

->(n/2^1 * 0) + (n/2^2 * 1)+ (n/2^3 * 2) + (n/2^4 * 3) +...+ (n/2^(h+1) * h)  
-> n * ( 0 + 1/4 + 2/8 + 3/16 +...+ h/2^(h+1) ) 

jetzt für jeden Wert von h die Folge

-> ( 0 + 1/4 + 2/8 + 3/16 +...+ h/2^(h+1) ) 

wird nie größer als 1 sein
Daher wird die Zeitkomplexität niemals größer sein als O(n) zum Aufbau von Haufen

Answer 5

Es wäre O(n log n), wenn man den Heap durch wiederholtes Einfügen von Elementen aufbauen würde. Sie können jedoch einen neuen Heap effizienter erstellen, indem Sie die Elemente in beliebiger Reihenfolge einfügen und dann einen Algorithmus anwenden, um sie in die richtige Reihenfolge zu bringen (was natürlich von der Art des Heaps abhängt).

Véase http://en.wikipedia.org/wiki/Binary_heap , "Aufbau eines Heaps" für ein Beispiel. In diesem Fall arbeiten Sie sich im Wesentlichen von der untersten Ebene des Baums nach oben, indem Sie Eltern- und Kindknoten austauschen, bis die Bedingungen für den Heap erfüllt sind.