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

"Die lineare Zeitschranke von build Heap lässt sich durch die Berechnung der Summe der Höhen aller Knoten im Heap, d.h. der maximalen Anzahl der gestrichelten Linien, zeigen. Für einen perfekten Binärbaum der Höhe h mit N = 2^(h+1) - 1 Knoten ist die Summe der Höhen der Knoten N - H - 1. Sie ist also O(N)."

Answer 2

Mir gefällt die Erklärung von Jeremy west.... sehr gut. Ein weiterer Ansatz, der wirklich leicht zu verstehen ist, wird hier gegeben http://courses.washington.edu/css343/zander/NotesProbs/heapcomplexity

da buildheap von heapify abhängt und der shiftdown-Ansatz verwendet wird, der von der Summe der Höhen aller Knoten abhängt. Um also die Summe der Höhe der Knoten zu finden, die gegeben ist durch S = Summation von i = 0 bis i = h von (2^i*(h-i)), wobei h = logn die Höhe des Baumes ist löst man s, so erhält man s = 2^(h+1) - 1 - (h+1) da n = 2^(h+1) - 1 s = n - h - 1 = n- logn - 1 s = O(n), und somit ist die Komplexität von buildheap O(n).

Answer 3

Nachweis von O(n)

Der Beweis ist nicht ausgefallen und ziemlich 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.