Durchschnittliche Zeit Komplexität für eine Entfernung von Minheap

Question

Die durchschnittliche Zeit Komplexität zu entfernen (d. H. RemoveMin auf einem Min-Heap) alle Elemente auf Heap in Reihenfolge?

Answer 1

Die Frage ist im Wesentlichen über Heapsort - Erstellen eines Min-Heap, und dann Elemente nacheinander zu entfernen, um eine sortierte Liste zu erstellen. Das Erstellen des Min-Heaps ist O (N) und diese Kosten werden von den Kosten für das Extrahieren der Elemente bestimmt. Der schlimmste Fall für die Extraktionsphase von Heapsort ist relativ einfach - jede Entfernung ist O (log N) und es gibt N von ihnen, so dass die Komplexität O (N log N) sein muss.

Dies bedeutet nicht, dass der Durchschnitt O (N log N) ist. Dafür brauchen wir Lower bound on heapsort?, um etwas schwieriger zu zeigen - nämlich, dass die beste Fallkomplexität für die Extraktionsphase auch Theta (N log N) ist.

Der Durchschnitt muss zwischen den besten (Theta (N log N)) und schlechtesten (O (N log N)) Fällen liegen, also ist Theta (N log N).