Kann jemand erklären, wie das Erstellen eines Heaps O (n) Komplexität sein kann?
Das Einfügen eines Elements in einen Heap erfolgt O(log n)
und das Einfügen wird n / 2 Mal wiederholt (der Rest sind Blätter und können die Heap-Eigenschaft nicht verletzen). Das heißt also, die Komplexität sollte sein O(n log n)
, denke ich.
Mit anderen Worten, für jedes Element, das wir "häufen", besteht die Möglichkeit, dass es für jede Ebene für den bisherigen Heap (dh log n Ebenen) einmal nach unten gefiltert werden muss.
Was vermisse ich?
Antworten:
Ich denke, in diesem Thema sind mehrere Fragen begraben:
buildHeap
damit es in O (n) Zeit ausgeführt wird?buildHeap
in O (n) -Zeit ausgeführt wird?Wie implementieren Sie,
buildHeap
damit es in O (n) Zeit ausgeführt wird?Oft konzentrieren sich die Antworten auf diese Fragen auf den Unterschied zwischen
siftUp
undsiftDown
. Die richtige Wahl zwischensiftUp
undsiftDown
zu treffen ist entscheidend, um die O (n) -Leistung zu erhaltenbuildHeap
, trägt jedoch nicht dazu bei, den Unterschied zwischenbuildHeap
undheapSort
im Allgemeinen zu verstehen . Tatsächlich richtige Implementierungen von beidenbuildHeap
undheapSort
wird nur verwendet werdensiftDown
. DiesiftUp
Operation wird nur benötigt, um Einfügungen in einen vorhandenen Heap durchzuführen, sodass sie beispielsweise zum Implementieren einer Prioritätswarteschlange unter Verwendung eines binären Heaps verwendet wird.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 anzeigen. Ein kleiner Haufen ist ebenfalls nützlich. Zum Beispiel beim Abrufen von Elementen mit Ganzzahlschlüsseln in aufsteigender Reihenfolge oder Zeichenfolgen in alphabetischer Reihenfolge. Die Prinzipien sind genau die gleichen; Wechseln Sie einfach die Sortierreihenfolge.
Die Heap-Eigenschaft gibt an, dass jeder Knoten in einem Binärheap mindestens so groß sein muss wie seine beiden untergeordneten Knoten. Dies bedeutet insbesondere, dass sich das größte Element im Heap im Stammverzeichnis befindet. Das Absenken und Aufwärtssieben ist im Wesentlichen dieselbe Operation 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 (wodurch er nach unten verschoben wird), bis er mindestens so groß ist wie beide Knoten darunter.siftUp
tauscht einen zu großen Knoten mit seinem übergeordneten Knoten aus (wodurch er nach oben verschoben wird), bis er nicht größer als der darüber liegende Knoten ist.Die Anzahl der Operationen , die erforderlich für die
siftDown
undsiftUp
ist proportional zum Abstand der Knoten bewegen müssen können. DennsiftDown
es ist der Abstand zum unteren Rand des Baums, dersiftDown
für Knoten am oberen Rand des Baums teuer ist. MitsiftUp
ist die Arbeit proportional zum Abstand zum oberensiftUp
Rand des Baums, daher ist sie für Knoten am unteren Rand 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. So sollte es nicht allzu überraschend sein , dass , wenn wir eine Operation an jeden Knoten anzuwenden haben, würden wir es vorziehen ,siftDown
übersiftUp
.Die
buildHeap
Funktion nimmt ein Array von unsortierten Elementen und verschiebt sie, bis sie alle die Heap-Eigenschaft erfüllen, wodurch ein gültiger Heap erzeugt wird. Es gibt zwei Ansätze, umbuildHeap
die von uns beschriebenen OperationensiftUp
und zusiftDown
verwenden.Beginnen Sie am oberen Rand des Heaps (am Anfang des Arrays) und rufen Sie
siftUp
jedes Element auf. Bei jedem Schritt bilden die zuvor gesiebten Elemente (die Elemente vor dem aktuellen Element im Array) einen gültigen Heap, und das Sieben des nächsten Elements platziert es an einer gültigen Position im Heap. Nach dem Durchsieben jedes Knotens erfüllen alle Elemente die Heap-Eigenschaft.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 wird ein Element gesiebt, bis es sich an der richtigen Stelle befindet.
Welche Implementierung für
buildHeap
ist effizienter?Beide Lösungen erzeugen einen gültigen Heap. Es ist nicht überraschend, dass die effizientere die zweite Operation ist, die verwendet wird
siftDown
.Sei h = log n die Höhe des Heaps. Die für den
siftDown
Ansatz erforderliche Arbeit ergibt sich aus der SummeJeder Term in der Summe hat die maximale Entfernung, die ein Knoten in der angegebenen 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
siftUp
beträgt die Summe für den Aufruf jedes KnotensEs sollte klar sein, dass die zweite Summe größer ist. Der erste Term allein ist hn / 2 = 1/2 n log n , so dass dieser Ansatz bestenfalls eine Komplexität von O (n log n) aufweist .
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 ignorieren, der Null ist:
Wenn Sie nicht sicher sind, warum jeder dieser Schritte funktioniert, finden Sie hier eine Begründung für den Prozess in Worten:
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 zu laufen , warum erfordert die Heap-Sortierung O (n log n) Zeit? Nun, die Heap-Sortierung besteht aus zwei Stufen. Zuerst rufen wirbuildHeap
das Array auf, das bei optimaler Implementierung O (n) Zeit benötigt . Der nächste Schritt besteht darin, das größte Element im Heap wiederholt zu löschen und am Ende des Arrays zu platzieren. Da wir ein Element aus dem Heap löschen, gibt es direkt nach dem Ende des Heaps immer eine freie Stelle, an der wir das Element speichern können. Die Heap-Sortierung erreicht also eine sortierte Reihenfolge, indem das nächstgrößere Element nacheinander entfernt und an der letzten Position in das Array eingefügt wird und sich nach vorne bewegt. Es ist die Komplexität dieses letzten Teils, die bei der Heap-Sortierung dominiert. Die Schleife sieht folgendermaßen aus:Es ist klar, dass die Schleife O (n) Mal ausgeführt wird ( n - 1 um genau zu sein, das letzte Element ist bereits vorhanden). Die Komplexität
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 handelt und daher eines der kleinsten Elemente ist. Diese neue Wurzel verletzt mit ziemlicher Sicherheit die Heap-Eigenschaft. Sie müssen also aufrufen,siftDown
bis Sie sie wieder in eine akzeptable Position bringen. Dies hat auch den Effekt, dass das nächstgrößere Element an die Wurzel verschoben wird. Beachten Sie, dassbuildHeap
wir im Gegensatz zu den meisten Knoten, die wirsiftDown
vom unteren Rand des BaumssiftDown
aus aufrufen, jetzt bei jeder Iteration vom oberen Rand 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 die untere Ebene vollständig entfernt haben). Dann ist für das nächste Quartal die Höhe h - 1 . Die Gesamtarbeit für diese zweite Stufe ist alsoBeachten Sie den Schalter: Jetzt entspricht der Null-Arbeitsfall einem einzelnen Knoten und der h- Arbeitsfall der Hälfte der Knoten. Diese Summe ist O (n log n), genau wie die ineffiziente Version
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 der Reihe nach zu entfernen , sodass die Komplexität O (n log n) ist . Sie können (unter Verwendung einiger Ideen aus der Informationstheorie) beweisen, dass für eine vergleichsbasierte Sortierung O (n log n) das Beste ist, auf das Sie hoffen können. Es gibt also keinen Grund, davon enttäuscht zu sein oder zu erwarten, dass die Heap-Sortierung das erreicht O (n) zeitgebunden
buildHeap
.quelle
siftUp
jedes Element aufrufen , oder Sie beginnen am Ende, wenn Sie sich rückwärts bewegen und anrufensiftDown
. Unabhängig davon, welchen Ansatz Sie wählen, wählen Sie das nächste Element im unsortierten Teil des Arrays aus und führen die entsprechende Operation aus, um es an eine gültige Position im geordneten Teil des Arrays zu verschieben. Der einzige Unterschied ist die Leistung.Ihre Analyse ist korrekt. Es ist jedoch nicht eng.
Es ist nicht einfach zu erklären, warum das Erstellen eines Heaps eine lineare Operation ist. Lesen Sie sie besser.
Eine große Analyse des Algorithmus zu sehen ist hier .
Die Hauptidee ist, dass im
build_heap
Algorithmus die tatsächlichenheapify
Kosten nichtO(log n)
für alle Elemente gelten.Wann
heapify
aufgerufen wird, hängt die Laufzeit davon ab, wie weit sich ein Element im Baum nach unten bewegen kann, bevor der Prozess beendet wird. Mit anderen Worten, es hängt von der Höhe des Elements im Heap ab. Im schlimmsten Fall kann das Element bis zur Blattebene abfallen.Zählen wir die geleistete Arbeit Stufe für Stufe.
Auf der untersten Ebene gibt es
2^(h)
Knoten, aber wir rufenheapify
keinen von diesen auf, daher ist die Arbeit 0. Auf der nächsten Ebene gibt es2^(h − 1)
Knoten, und jeder kann sich um 1 Ebene nach unten bewegen. Auf der 3. Ebene von unten befinden sich2^(h − 2)
Knoten, die sich jeweils um 2 Ebenen nach unten bewegen können.Wie Sie sehen können, sind nicht alle Heapify-Vorgänge
O(log n)
, weshalb Sie erhaltenO(n)
.quelle
Heapify
istO(n)
wenn fertig,siftDown
aberO(n log n)
wenn fertigsiftUp
. Die eigentliche Sortierung (einzelnes Ziehen von Elementen aus dem Haufen) musssiftUp
daher durchgeführt werdenO(n log n)
.i
vom unteren Rand eines Baums der Höhe h durchgeführt wurden, ebenfalls2* log(h-i)
Vergleiche durchführen müssen und auch bei The111 berücksichtigt werden sollten. Was denken Sie?Intuitiv:
Nicht ganz. Ihre Logik erzeugt keine enge Grenze - sie überschätzt die Komplexität jedes Heapify. Wenn von unten nach oben gebaut, kann das Einfügen (Heapify) viel geringer sein als
O(log(n))
. Der Prozess ist wie folgt:(Schritt 1) Die ersten
n/2
Elemente befinden sich in der unteren Reihe des Heaps.h=0
Heapify wird also nicht benötigt.(Schritt 2) Die nächsten Elemente werden in der Zeile 1 von unten nach oben verschoben. , Heapify Filter 1 Ebene nach unten.
n/22
h=1
(Schritt i ) Die nächsten Elemente werden von unten nacheinander angeordnet . , Heapify Filter Ebenen nach unten.
n/2i
i
h=i
i
(Schrittprotokoll (n) ) Das letzte Element wird von unten in einer Reihe nach oben verschoben. , Heapify Filter Ebenen nach unten.
n/2log2(n) = 1
log(n)
h=log(n)
log(n)
HINWEIS: Nach Schritt 1 befinden sich
1/2
die Elemente(n/2)
bereits im Heap, und wir mussten Heapify nicht einmal aufrufen. Beachten Sie auch, dass nur ein einziges Element, die Wurzel, tatsächlich die vollelog(n)
Komplexität aufweist.Theoretisch:
Die Gesamtschritte
N
zum Erstellen eines Größenhaufensn
können mathematisch ausgeschrieben werden.In der Höhe
i
haben wir (oben) gezeigt, dass es Elemente gibt, die Heapify aufrufen müssen, und wir wissen, dass Heapify in der Höhe ist . Das gibt:n/2i+1
i
O(i)
Die Lösung für die letzte Summierung kann gefunden werden, indem die Ableitung beider Seiten der bekannten geometrischen Reihengleichung genommen wird:
Schließlich
x = 1/2
ergibt das Einstecken in die obige Gleichung2
. Wenn Sie dies in die erste Gleichung einfügen, erhalten Sie:Somit ist die Gesamtzahl der Schritte von Größe
O(n)
quelle
Es wäre O (n log n), wenn Sie den Heap durch wiederholtes Einfügen von Elementen erstellen würden. 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 der richtigen Reihenfolge zu "heapifizieren" (natürlich abhängig von der Art des Heaps).
Ein Beispiel finden Sie unter http://en.wikipedia.org/wiki/Binary_heap , "Erstellen eines Heaps". In diesem Fall arbeiten Sie im Wesentlichen von der untersten Ebene des Baums aus und tauschen übergeordnete und untergeordnete Knoten aus, bis die Heap-Bedingungen erfüllt sind.
quelle
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 mit der Höhe 0 (hier 23/2 = 12),n/2^2
rote Knoten mit der Höhe 1 (hier 23/4 = 6),n/2^3
blaue Knoten mit der Höhe 2 (hier 23/8 = 3).n/2^4
lila Knoten mit der Höhe 3 (hier 23/16 = 2),also gibt es
n/2^(h+1)
Knoten für die Höhe h.Um die Zeitkomplexität zu ermitteln, können Sie den Arbeitsaufwand oder die maximale Anzahl der von jedem Knoten durchgeführten Iterationen zählen.
Jetzt kann festgestellt werden, dass jeder Knoten dies kann (höchstens) Iterationen durchführen == Höhe des Knotens
Für alle Knoten mit der Höhe h beträgt die maximal geleistete Arbeit n / 2 ^ (h + 1) * h
Jetzt ist die gesamte Arbeit erledigt
nun für jeden Wert von h die Sequenz
wird niemals 1 überschreiten.
Somit wird die Zeitkomplexität niemals O (n) für den Gebäudehaufenüberschreiten
quelle
Wie wir wissen, ist die Höhe eines Heaps log (n) , wobei n die Gesamtzahl der Elemente ist. Stellen wir es als h dar.
Wenn wir eine Heapify-Operation ausführen, bewegen sich die Elemente auf der letzten Ebene ( h ) nicht einmal ein einziges Schritt.
Die Anzahl der Elemente auf der vorletzten Ebene ( h-1 ) beträgt 2 h-1 und sie können sich auf maximal 1 Ebene bewegen (während des Heapify).
In ähnlicher Weise für den i - ten , Ebene haben wir 2 i Elemente , die bewegen kann hallo Positionen.
Daher ist die 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 ist die AGP- Serie, um diese Teilung beider Seiten durch 2
S / 2 = 2 h {1/2 zu lösen 2 + 2/2 3 + ... h / 2 h + 1 } --------------------------------- ---------------- 2
Subtrahieren von 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 }
nun 1/2 + 1/2 2 + 1/2 3 + ... + 1/2 h verringert GP, dessen Summe kleiner als 1 ist (wenn h gegen unendlich geht, tendiert die Summe gegen 1). In der weiteren Analyse nehmen wir eine Obergrenze für die Summe, die 1 ist.
Dies ergibt S = 2 h + 1 {1 + h / 2 h + 1 }
= 2 h + 1 + h
~ 2 h + h
als h = log (n) , 2 h = n
Daher ist S = n + log (n)
T (C) = O (n)
quelle
Nehmen wir an, Sie gehen beim Erstellen eines Haufens von unten nach oben vor.
quelle
Beim Erstellen des Heaps beginnen wir mit der Höhe logn -1 (wobei logn die Höhe des Baums von n Elementen ist). Für jedes Element, das in der Höhe 'h' vorhanden ist, gehen wir mit maximaler Höhe (logn -h) nach unten.
quelle
Aufeinanderfolgende Einfügungen können beschrieben werden durch:
Durch Star Näherung
n! =~ O(n^(n + O(1)))
daherT =~ O(nlog(n))
Ich hoffe, dies hilft. Der optimale Weg
O(n)
ist die Verwendung des Build-Heap-Algorithmus für einen bestimmten Satz (Reihenfolge spielt keine Rolle).quelle
Grundsätzlich wird beim Erstellen eines Heaps nur an Nicht-Blattknoten gearbeitet ... und die Arbeit ist die Menge des Austauschs, um die Heap-Bedingung zu erfüllen ... mit anderen Worten (im schlimmsten Fall) ist die Menge proportional zur Höhe des Knotens ... Alles in allem ist die Komplexität des Problems proportional zur Summe der Höhen aller Nicht-Blattknoten. Dies ist (2 ^ h + 1 - 1) -h-1 = nh-1 = Auf)
quelle
@bcorso hat bereits den Beweis für die Komplexitätsanalyse erbracht. Aber für diejenigen, die noch Komplexitätsanalyse lernen, muss ich Folgendes hinzufügen:
Die Grundlage Ihres ursprünglichen Fehlers liegt in einer Fehlinterpretation der Bedeutung der Aussage "Das Einfügen in einen Heap dauert 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 Heaps wie beim Einfügen i ist. Nur die letzte Einfügung hat eine Komplexität von O (log n).
quelle
Nehmen wir an, Sie haben N Elemente in einem Heap. Dann wäre seine Höhe Log (N)
Nun wollen Sie ein anderes Element einzufügen, dann ist die Komplexität wäre: Log (N) , müssen wir den ganzen Weg vergleichen UP an der Wurzel.
Jetzt haben Sie N + 1 Elemente & height = Log (N + 1)
Mit Hilfe der Induktionstechnik kann nachgewiesen werden, dass die Komplexität der Insertion ∑logi wäre .
Jetzt mit
Dies vereinfacht sich zu: ∑logi = log (n!)
das ist eigentlich O (NlogN)
Aber
wir machen hier etwas falsch, da wir in allen Fällen nicht oben ankommen. Während wir dies meistens ausführen, werden wir feststellen, dass wir nicht einmal auf halber Höhe des Baumes sind. Woher kann diese Grenze optimiert werden, um eine andere engere Grenze zu haben, indem die in den obigen Antworten angegebene Mathematik verwendet wird.
Diese Erkenntnis kam mir nach einem Detail und Experimenten auf Haufen.
quelle
Ich mag Erklärungen von Jeremy West sehr ... ein anderer Ansatz, der wirklich leicht zu verstehen ist, wird hier gegeben: http://courses.washington.edu/css343/zander/NotesProbs/heapcomplexity
da Buildheap abhängig von Heapify hängt und Shiftdown-Ansatz verwendet wird, der von der Summe der Höhen aller Knoten abhängt. Um also die Summe der Knotenhöhen 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 des Buildheap O (n).
quelle
"Die lineare Zeitgrenze des Build-Heaps kann angezeigt werden, indem die Summe der Höhen aller Knoten im Heap berechnet wird, die die maximale Anzahl gestrichelter Linien darstellt. Für den perfekten binären Baum der Höhe h mit N = 2 ^ ( h + 1) - 1 Knoten, die Summe der Höhen der Knoten ist N - H - 1. Somit ist es O (N). "
quelle
Beweis von O (n)
Der Beweis ist nicht ausgefallen und recht einfach. Ich habe nur den Fall für einen vollständigen Binärbaum bewiesen. Das Ergebnis kann für einen vollständigen Binärbaum verallgemeinert werden.
quelle
Wir erhalten die Laufzeit für den Heap-Build, indem wir die maximale Bewegung ermitteln, die jeder Knoten ausführen kann. Wir müssen also wissen, wie viele Knoten sich in jeder Zeile befinden und wie weit jeder Knoten von ihnen entfernt sein kann.
Ausgehend vom Wurzelknoten hat jede nächste Zeile doppelt so viele Knoten wie die vorherige Zeile. Wenn wir also antworten, wie oft wir die Anzahl der Knoten verdoppeln können, bis keine Knoten mehr vorhanden sind, erhalten wir die Höhe des Baums. Oder mathematisch gesehen ist die Höhe des Baums log2 (n), wobei n die Länge des Arrays ist.
Um die Knoten in einer Zeile zu berechnen, beginnen wir von hinten. Wir wissen, dass sich n / 2 Knoten unten befinden. Wenn Sie also durch 2 teilen, erhalten Sie die vorherige Zeile und so weiter.
Basierend darauf erhalten wir diese Formel für den Siftdown-Ansatz: (0 * n / 2) + (1 * n / 4) + (2 * n / 8) + ... + (log2 (n) * 1)
Der Term in der letzten Paranthesis ist die Höhe des Baums multipliziert mit dem einen Knoten, der sich an der Wurzel befindet. Der Term in der ersten Paranthesis sind alle Knoten in der unteren Reihe multipliziert mit der Länge, die sie zurücklegen können, 0. Gleiche Formel in smart:
Wenn wir das n zurückbringen, haben wir 2 * n, 2 kann verworfen werden, da es eine Konstante ist und wir die Worst-Case-Laufzeit des Siftdown-Ansatzes haben: n.
quelle
Ich denke, du machst einen Fehler. Schauen Sie sich das an: http://golang.org/pkg/container/heap/ Das Erstellen eines Haufens ist nicht O (n). Das Einfügen ist jedoch O (lg (n). Ich gehe davon aus, dass die Initialisierung O (n) ist, wenn Sie eine Heap-Größe b / c festlegen. Der Heap muss Speicherplatz zuweisen und die Datenstruktur einrichten. Wenn Sie n Elemente zum Einfügen haben in den Haufen dann ja, jede Einfügung ist lg (n) und es gibt n Elemente, so dass Sie n * lg (n) erhalten, wie u angegeben
quelle