webentwicklung-frage-antwort-db.com.de

Wie kann ein Haufen gebaut werden? O(n) zeitliche Komplexität?

Kann jemand helfen, zu erklären, wie der Aufbau eines Haufens O(n) Komplexität sein kann? 

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

Mit anderen Worten, für jedes Element, das wir "heapifizieren", besteht die Möglichkeit, dass es für jede Ebene für den bisherigen Heap (die log n-Stufen ist) einmal herunterfiltern muss.

Was vermisse ich?

351
GBa

Ich denke, es gibt mehrere Fragen in diesem Thema begraben:

  • Wie implementieren Sie buildHeap, sodass es in O (n) Zeit ausgeführt wird?
  • Wie zeigen Sie, dass buildHeap bei korrekter Implementierung in der Zeit O (n) abläuft?
  • Warum funktioniert dieselbe Logik nicht, um die Heap-Sortierung in O (n) anstatt O (n log n) auszuführen? )?

Wie implementieren Sie buildHeap, sodass es in O (n) Zeit ausgeführt wird?

Die Antworten auf diese Fragen konzentrieren sich häufig auf den Unterschied zwischen siftUp und siftDown. Die richtige Wahl zwischen siftUp und siftDown zu treffen, ist entscheidend, um O (n) Leistung für buildHeap zu erzielen, hilft aber nichts Verstehe den Unterschied zwischen buildHeap und heapSort im Allgemeinen. In der Tat wird bei ordnungsgemäßen Implementierungen von buildHeap und heapSortnursiftDown verwendet. Die siftUp -Operation ist nur erforderlich, um Einfügungen in einen vorhandenen Heap durchzuführen. Sie wird daher beispielsweise zum Implementieren einer Prioritätswarteschlange mithilfe eines Binärheaps verwendet.

Ich habe dies geschrieben, um zu beschreiben, wie ein maximaler Heap funktioniert. Dies ist der Heap-Typ, der normalerweise für die Heap-Sortierung oder für eine Prioritätswarteschlange verwendet wird, bei der höhere Werte eine höhere Priorität angeben. Ein kleiner Haufen ist ebenfalls nützlich. Zum Beispiel beim Abrufen von Elementen mit ganzzahligen Schlüsseln in aufsteigender Reihenfolge oder von Zeichenfolgen in alphabetischer Reihenfolge. Die Prinzipien sind genau die gleichen; einfach die sortierreihenfolge wechseln.

Die Heap-Eigenschaft ​​gibt an, dass jeder Knoten in einem binären Heap mindestens so groß sein muss wie die beiden untergeordneten Knoten. Dies impliziert insbesondere, dass sich das größte Element im Heap an der Wurzel befindet. Herunterschieben und Heraufsieben sind im Wesentlichen die gleichen Vorgänge in entgegengesetzte Richtungen: Verschieben Sie einen fehlerhaften Knoten, bis er die Heap-Eigenschaft erfüllt:

  • siftDown tauscht einen zu kleinen Knoten mit seinem größten Kind aus (verschiebt ihn dabei nach unten), bis er mindestens so groß ist wie beide Knoten darunter.
  • siftUp tauscht einen zu großen Knoten mit dem übergeordneten Knoten aus (verschiebt ihn dabei nach oben), bis er nicht größer als der Knoten darüber ist.

Die Anzahl der Operationen, die für siftDown und siftUp erforderlich sind, ist proportional zur Entfernung, die der Knoten möglicherweise zurücklegen muss. Für siftDown ist dies der Abstand zum unteren Ende des Baums, sodass siftDown für Knoten am oberen Ende des Baums teuer ist. Mit siftUp ist die Arbeit proportional zum Abstand zum oberen Ende des Baums, daher ist siftUp für Knoten am unteren Ende des Baums teuer. Obwohl beide Operationen im schlimmsten Fall O (log n) sind, befindet sich in einem Heap nur ein Knoten oben, während die Hälfte der Knoten in der unteren Schicht liegt. Also es sollte nicht allzu überraschend sein, dass wir, wenn wir eine Operation auf jeden Knoten anwenden müssen, siftDown vor siftUp bevorzugen.

Die Funktion buildHeap nimmt ein Array unsortierter Elemente und verschiebt sie, bis alle die Eigenschaft heap erfüllen, wodurch ein gültiger Heap erstellt wird. Es gibt zwei Ansätze, die für buildHeap mit den beschriebenen siftUp - und siftDown -Operationen verwendet werden können.

  1. Beginnen Sie oben auf dem Heap (am Anfang des Arrays) und rufen Sie siftUp für jedes Element auf. Bei jedem Schritt bilden die zuvor gesiebten Elemente (die Elemente vor dem aktuellen Element im Array) einen gültigen Heap, und beim Sichten des nächsten Elements nach oben wird dieser an eine gültige Position im Heap verschoben. Nach dem Durchsuchen jedes Knotens erfüllen alle Elemente die Heap-Eigenschaft.

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

Welche Implementierung für buildHeap ist effizienter?

Beide Lösungen führen zu einem gültigen Heap. Es überrascht nicht, dass die effizientere die zweite Operation ist, die siftDown verwendet.

Es sei h = log n die Höhe des Haufens. Die für den Ansatz siftDown erforderliche Arbeit ergibt sich aus der 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 angegebenen Höhe zurücklegen muss (Null für die unterste Ebene, h für die Wurzel), multipliziert mit der Anzahl der Knoten in dieser Höhe. Im Gegensatz dazu beträgt die Summe für den Aufruf von siftUp auf jedem Knoten

(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 , daher ist dieser Ansatz bestenfalls komplex O (n log n) .

Wie beweisen wir, dass die Summe für den siftDown -Ansatz tatsächlich O (n) ist?

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

Taylor series for buildHeap complexity

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

  • Die Terme sind alle positiv, daher muss die endliche Summe kleiner sein als die unendliche Summe.
  • Die Reihe entspricht einer Potenzreihe, die mit x = 1/2 bewertet wird.
  • Diese Potenzreihe entspricht (zu konstanten Zeiten) der Ableitung der Taylor-Reihe für f (x) = 1/(1-x) .
  • x = 1/2 liegt innerhalb des Konvergenzintervalls dieser Taylorreihe.
  • Daher können wir die Taylor-Reihe durch 1/(1-x) ersetzen, differenzieren und auswerten, um den Wert der unendlichen Reihe zu ermitteln.

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

Warum benötigt die Heap-Sortierung O (n log n) Zeit?

Wenn es möglich ist, buildHeap in linearer Zeit auszuführen, warum erfordert die Heap-Sortierung O (n log n) Zeit? Nun, die Heap-Sortierung besteht aus zwei Stufen. Zuerst rufen wir buildHeap auf dem Array auf, was O (n) Zeit erfordert, wenn es optimal implementiert ist. In der nächsten Phase löschen Sie wiederholt das größte Element im Heap und platzieren es am Ende des Arrays. Da wir ein Objekt aus dem Heap löschen, ist unmittelbar nach dem Ende des Heap immer eine Stelle frei, an der wir das Objekt speichern können. Die Heap-Sortierung führt also zu einer sortierten Reihenfolge, indem das nächstgrößere Element nacheinander entfernt und beginnend an der letzten Position in das Array eingefügt und nach vorne verschoben wird. Es ist die Komplexität dieses letzten Teils, die bei der Heap-Sortierung dominiert. Die Schleife sieht so aus:

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

Natürlich läuft die Schleife O(n) mal ( n - 1 um genau zu sein, das letzte Element ist bereits vorhanden) . Die Komplexität von deleteMax für einen Heap ist O (log n) . Es wird normalerweise implementiert, indem der Stamm (das größte im Heap verbleibende Element) entfernt und durch das letzte Element im Heap ersetzt wird, bei dem es sich um ein Blatt und damit um eines der kleinsten Elemente handelt. Dieser neue Stamm verletzt mit ziemlicher Sicherheit die Heap-Eigenschaft, sodass Sie siftDown aufrufen müssen, bis Sie ihn wieder in eine akzeptable Position bringen. Dies hat auch den Effekt, dass das nächstgrößere Objekt zur Wurzel verschoben wird. Beachten Sie, dass wir im Gegensatz zu buildHeap, bei dem die meisten Knoten siftDown vom unteren Ende des Baums aufrufen, bei jeder Iteration siftDown vom oberen Ende des Baums aus aufrufen ! Obwohl der Baum schrumpft, schrumpft er nicht schnell genug : Die Höhe des Baums bleibt konstant, bis Sie die erste Hälfte der Knoten entfernt haben (wenn Sie den Boden entfernen) Schicht vollständig). Dann ist für das nächste Quartal die Höhe h - 1 . Die Gesamtarbeit für diese zweite Stufe ist also

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

Beachten Sie den Schalter: Jetzt entspricht der Nullarbeitsfall einem einzelnen Knoten und der h Arbeitsfall entspricht der Hälfte der Knoten. Diese Summe ist O (n log n) genau wie die ineffiziente Version von buildHeap, die mit siftUp implementiert wird. In diesem Fall haben wir jedoch keine Wahl, da wir versuchen zu sortieren und das nächstgrößere Element als nächstes entfernt werden muss.

Zusammenfassend ist die Arbeit für die Heap-Sortierung die Summe der beiden Stufen: O (n) Zeit für buildHeap und O (n log n), um jeden Knoten in der angegebenen Reihenfolge zu entfernen Die Komplexität ist also O (n log n) . Sie können (mit einigen Ideen aus der Informationstheorie) beweisen, dass O (n log n) für eine vergleichende Sortierung das Beste ist, auf das Sie hoffen können, also gibt es keinen Grund von diesem enttäuscht zu sein oder zu erwarten, dass die Heap-Sortierung die O(n) Zeitgrenze erreicht, die buildHeap erfüllt.

321
Jeremy West

Ihre Analyse ist korrekt. Es ist jedoch nicht eng. 

Es ist nicht wirklich einfach zu erklären, warum das Erstellen eines Heapspeichers eine lineare Operation ist. Sie sollten sie besser lesen.

Eine große Analyse des Algorithmus ist hier zu sehen.


Die Hauptidee ist, dass im build_heap-Algorithmus die tatsächlichen heapify-Kosten nicht für alle Elemente O(log n) sind.

Wenn heapify aufgerufen wird, hängt die Laufzeit davon ab, wie weit sich ein Element in der Baumstruktur nach unten bewegt, bevor der Prozess beendet wird. Mit anderen Worten, es hängt von der Höhe des Elements im Heap ab. Im schlimmsten Fall geht das Element möglicherweise bis zur Blattebene hinunter. 

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

Auf der untersten Ebene gibt es 2^(h)-Knoten, wir rufen jedoch keine heapify auf, also ist die Arbeit 0. Auf der nächsten Ebene gibt es 2^(h − 1)-Knoten, die sich jeweils um 1 Ebene nach unten bewegen können. Auf der dritten Ebene von unten gibt es 2^(h − 2)-Knoten, und jeder kann sich um 2 Ebenen nach unten bewegen.

Da nicht alle Heapify-Operationen O(log n) sind, erhalten Sie O(n).

286

Intuitiv:

"Die Komplexität sollte O (nLog n) sein ... für jedes Element, das wir" heapifizieren ", besteht die Möglichkeit, dass Sie für jedes Level für den Heap (das heißt log n-Level) einmal herunterfiltern muss.

Nicht ganz. Ihre Logik erzeugt keine engen Grenzen - sie überschätzt die Komplexität jedes Heapizes. Wenn von unten nach oben gebaut, kann das Einfügen (heapify) viel weniger als O(log(n)) sein. Der Prozess ist wie folgt:

(Schritt 1) ​​Die ersten n/2-Elemente werden in der untersten Zeile des Heapspeichers angezeigt. h=0, daher ist keine Heapifizierung erforderlich.

(Schritt 2) Die nächsten n/22-Elemente gehen von unten in die erste Zeile. h=1, heapify filtert 1 Ebene nach unten.

(Schritt i) Die nächsten n/2i-Elemente werden in der Reihe i von unten nach oben verschoben. h=i, heapify filtert i.

(Schritt log (n)) Das letzte n/2log2(n) = 1-Element geht von unten in die Zeile log(n). h=log(n), heapify-Filter log(n) nimmt ab.

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


Theoretisch:

Die Gesamtschritte N, um einen Heap der Größe n zu erstellen, können mathematisch geschrieben werden. 

Bei Höhe i haben wir (oben) gezeigt, dass es n/2i+1 Elemente gibt, die heapify aufrufen müssen, und wir wissen, dass heapify bei Höhe iO(i) ist. Das gibt:

enter image description here

Die Lösung der letzten Summation kann gefunden werden, indem die Ableitung beider Seiten der bekannten geometrischen Reihengleichung genommen wird:

enter image description here

Das Einfügen von x = 1/2 in die obige Gleichung ergibt 2. Das Einfügen in die erste Gleichung ergibt:

enter image description here

Somit ist die Gesamtzahl der Schritte von der Größe O(n)

83
bcorso

Es wäre O (n log n), wenn Sie den Heap durch wiederholtes Einfügen von Elementen erstellen. Sie können jedoch einen neuen Heap-Speicher effizienter erstellen, indem Sie die Elemente in beliebiger Reihenfolge einfügen und anschließend einen Algorithmus anwenden, um sie in der richtigen Reihenfolge zu "heapifizieren" (abhängig vom Heap-Typ).

Siehe http://en.wikipedia.org/wiki/Binary_heap , "Einen Haufen erstellen" für ein Beispiel. In diesem Fall arbeiten Sie im Wesentlichen von der untersten Ebene der Baumstruktur aus und tauschen übergeordnete und untergeordnete Knoten aus, bis die Heap-Bedingungen erfüllt sind. 

32
mike__t

Wie wir wissen, ist die Höhe eines Heaps log (n) , wobei n die Gesamtzahl der Elemente ist. Lets stellen sie als h dar
Wenn wir die Heapifizierungsoperation ausführen, bewegen sich die Elemente auf der letzten Ebene ( h ) nicht einmal um einen Schritt.
Die Anzahl der Elemente auf der vorletzten Ebene ( h-1 ) beträgt 2 h-1 und sie können sich bei max 1 level bewegen (während der Heapifizierung). 
Ähnlich für die i th , Ebene haben wir 2 ich Elemente, die h-i Positionen verschieben können.

Daher Gesamtzahl der Züge =S= 2 h * 0 + 2 h-1 * 1 + 2 h-2 * 2 + ... 2 0 * h

S = 2 h {1/2 + 2/2 2 + 3/2 3 + ... h/2 h } --------------------------------------------- 1
Dies istAGPseries, um diese beiden Seiten durch 2 zu lösen
S/2 = 2 h {1/2 2 + 2/2 3 + ... h/2 h + 1 } ----------------------------------------- ---- 2
Subtraktion der Gleichung 2 von 1 ergibt
S/2 = 2 h {1/2 + 1/2 2 + 1/2 3 + ... + 1/2 h + h/2 h + 1 }
S = 2 h + 1 {1/2 + 1/2 2 + 1/2 3 + ... + 1/2 h + h/2 h + 1 }
jetzt 1/2 + 1/2 2 + 1/2 3 + ... + 1/2 h sinktGP, dessen Summe kleiner ist als 1 (wenn h zur Unendlichkeit neigt, tendiert die Summe zu 1). Nehmen wir zur weiteren Analyse eine obere Grenze für die Summe von 1 an. 
Dies ergibt S = 2 h + 1 {1 + h/2 h + 1 }
= 2 h + 1 + h
~ 2 h + h
as h = log (n) , 2 h = n

Daher ist S = n + log (n)
T (C) = O (n)

7
Tanuj Yadav

Nehmen wir an, Sie bauen einen Haufen und gehen von unten nach oben.

  1. Sie nehmen jedes Element und vergleichen es mit seinen untergeordneten Elementen, um zu überprüfen, ob das Paar den Heap-Regeln entspricht. Daher werden die Blätter kostenlos in den Haufen aufgenommen. Das liegt daran, dass sie keine Kinder haben. 
  2. Nach oben wäre der ungünstigste Fall für den Knoten direkt über den Blättern ein Vergleich (max. Würde mit nur einer Generation von Kindern verglichen)
  3. Wenn sie weiter nach oben gehen, können ihre unmittelbaren Eltern maximal mit zwei Generationen von Kindern verglichen werden. 
  4. Wenn Sie in derselben Richtung fortfahren, haben Sie im schlimmsten Fall log (n) Vergleiche für die Wurzel. und log (n) -1 für seine unmittelbaren Kinder, log (n) -2 für ihre unmittelbaren Kinder und so weiter.
  5. Wenn Sie also alles zusammenfassen, kommen Sie auf etwas wie log (n) + {log (n) -1} * 2 + {log (n) -2} * 4 + ..... + 1 * 2 ^ {( logn) -1} was nichts als O (n) ist. 
5
Jones

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

enter image description here

Nun schauen Sie sich das Bild an, es gibt
n/2^1grüne Knotenmit Höhe 0 (hier 23/2 = 12)
n/2^2rote Knotenmit Höhe 1 (hier 23/4 = 6)
n/2^3blauer Knotenmit Höhe 2 (hier 23/8 = 3)
n/2^4lila Knotenmit Höhe 3 (hier 23/16 = 2)
so gibt es n/2^(h+1) Knoten für die Höheh
Um die zeitliche Komplexität zu ermitteln, können Sie Menge der geleisteten Arbeitoder max. Anzahl der durchgeführten Iterationenvon jedem Knoten) zählen
Jetzt ist zu bemerken, dass jeder Knoten (höchstens) Iterationen == Höhe des Knotens ausführen kann.

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/4^3 * 3  

so ist für jedenKnoten mit der Höhe hmaximale geleistete Arbeit n/2 ^ (h + 1) * h

Jetzt ist die gesamte Arbeit erledigt

->(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 vonh, die Sequenz

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

wird niemals 1 überschreiten
Somit wird die Zeitkomplexität niemalsO(n)zum Bauen von Haufen überschreiten

3
Julkar9

Wenn wir den Haufen bauen, beginnen wir von der Höhe, logn -1 (wobei logn die Baumhöhe von n Elementen ist). Für jedes Element in der Höhe 'h' gehen wir um max.

    So total number of traversal would be:-
    T(n) = sigma((2^(logn-h))*h) where h varies from 1 to logn
    T(n) = n((1/2)+(2/4)+(3/8)+.....+(logn/(2^logn)))
    T(n) = n*(sigma(x/(2^x))) where x varies from 1 to logn
     and according to the [sources][1]
    function in the bracket approaches to 2 at infinity.
    Hence T(n) ~ O(n)
2
Kartik Goyal

Aufeinanderfolgende Einfügungen können beschrieben werden durch: 

T = O(log(1) + log(2) + .. + log(n)) = O(log(n!))

Durch starre Annäherung n! =~ O(n^(n + O(1))), also T =~ O(nlog(n))

Ich hoffe, das hilft, die optimale Art und Weise, wie O(n) den Build-Heap-Algorithmus für eine gegebene Menge verwendet (Reihenfolge spielt keine Rolle).

1
Tomer Shalev

Nachweis von O(n)

Der Beweis ist nichts Besonderes, und ziemlich unkompliziert, ich habe nur den Fall eines vollständigen binären Baums bewiesen, das Ergebnis kann für einen vollständigen binären Baum verallgemeinert werden.

1
Yi Y

@bcorso hat bereits den Beweis der Komplexitätsanalyse bewiesen. Aber für diejenigen, die noch Komplexitätsanalyse lernen, muss ich Folgendes hinzufügen:

Die Grundlage Ihres ursprünglichen Fehlers liegt in einer falschen Interpretation der Bedeutung der Anweisung: "Das Einfügen in einen Heap benötigt O (log n) Zeit". Das Einfügen in einen Heap ist zwar O (log n), aber Sie müssen erkennen, dass n die Größe des Heaps während des Einfügens ist.

Im Zusammenhang mit dem Einfügen von n Objekten in einen Heap ist die Komplexität der i-ten Einfügung O (log n_i), wobei n_i die Größe des Heap wie beim Einfügen i ist. Nur die letzte Einfügung hat eine Komplexität von O (log n).

1
N.Vegeta

Grundsätzlich wird nur an Nicht-Blatt-Knoten gearbeitet, während ein Heap erstellt wird. Als Arbeit wird der Umfang des Austauschs verwendet, um die Heap-Bedingung zu erfüllen. Mit anderen Worten (im schlimmsten Fall) ist der Umfang proportional zur Höhe des Knotens ... Alles in allem ist die Komplexität des Problems proportional zur Summe der Höhen aller Nicht-Blattknoten. (2 ^ h + 1 - 1) -h-1 = nh-1 = Auf)

1
Shubham Jindal

Nehmen wir an, Sie haben N Elemente in einem Haufen. Dann wäre seine Höhe Log (N)

Jetzt möchten Sie ein anderes Element einfügen, dann wäre die Komplexität: Log (N), wir müssen den gesamten Weg BIS mit dem Stamm vergleichen.

Jetzt haben Sie N + 1 Elemente & Höhe = Log (N + 1)

Mit der induction - Technik kann nachgewiesen werden, dass die Komplexität der Einfügung ∑logi wäre. 

Jetzt mit 

log a + log b = log ab

Dies vereinfacht sich zu: ∑logi = log (n!)

welches ist eigentlich O(NlogN)

Aber

wir machen hier etwas falsch, da wir in allen Fällen nicht an die Spitze gelangen. Daher werden wir bei der Ausführung meistens feststellen, dass wir nicht einmal die Hälfte des Baumes erreichen. Daher kann diese Schranke unter Verwendung der in den obigen Antworten angegebenen Mathematik für eine weitere engere Schranke optimiert werden.

Diese Erkenntnis kam mir jedoch nach einem Detail und Experimenten an Heaps.

0
Fooo

Ich mag Erklärungen von Jeremy West sehr gerne ... ein anderer Ansatz, der für das Verständnis sehr einfach ist, wird hier angegeben http://courses.washington.edu/css343/zander/NotesProbs/heapcomplexity

da die Verwendung von Buildheap von Heapify abhängt, wird ein Shiftdown-Ansatz verwendet, der von der Summe der Höhen aller Knoten abhängt. Also, um die Summe der Höhe der Knoten zu finden, die durch S = Summation von i = 0 bis i = h von (2 ^ i * (hi)) gegeben ist, wobei h = logn die Höhe der Baumlösung s ist, erhalten wir s = 2 ^ (h + 1) - 1 - (h + 1), da n = 2 ^ (h + 1) - 1 s = n - h - 1 = n - logn - 1 s = O (n), und so ist die Komplexität von buildheap O (n).

0
Nitish Jain

"Die lineare Zeitbegrenzung von build Heap kann durch Berechnen der Summe der Höhen aller Knoten im Heap angezeigt werden. Dies ist die maximale Anzahl von gestrichelten Linien .. _ 2 ^ (h + 1) - 1 Knoten, die Summe der Höhen der Knoten ist N - H - 1 . Es ist also O (N). "

0
sec3