Komplexität von heapify auf einer linken Haufen Warteschlange

Question

„Datenstrukturen und Netzwerkalgorithmen“ von Tarjan heißt es in der heapify Funktion in leftiest heaps, wie folgend:

heap function heapify (list q); 
    do |q| ≥ 2 → := q[3..] & meld (q(1), q(2)) od; 
    return if q = [ ] → null | q != [ ] → q(1) fi 
end heapify; 

q wird die Warteschlange von Halden würden wir gemeinsam heapify mögen. meld(h1, h2) ist eine Funktion zum Zusammenführen von zwei Heaps und Wiederherstellen der Heap-Eigenschaft. meld(h1, h2) hat die Komplexität O (logn), wobei n die Gesamtzahl der Knoten in beiden Heaps ist. Dies macht die Komplexität für einen Durchgang durch die Warteschlange, wie folgend:

(Eq. 1)

die plausibel ist. Was ich nicht bekommen, ist die Zeit für die gesamte heapify wie es ist:

(Gl. 2)

k hier ist die Anzahl der Originalhaufen und n die Gesamtzahl der Elemente, die sie enthalten. Darüber hinaus gibt es zwei vorher erwähnt Constraints:

(Eq. 3)

Kann jemand mir helfen, zu verstehen, wie die Gl. 2 ist abgeleitet? (., Wie man die linke Ausdruck der Gleichheit in Gleichung interpretiert 2)

Answer 1

ich die Lösung herausgefunden, was ziemlich offensichtlich, erwies sich als:

in jeder Iteration wird die Anzahl der Warteschlangenelemente halbiert. Dies macht es k/2 pro Iteration. Bei Betrachtung aller Iterationen schrumpft die Zahl exponentiell zur Basis von 2, d. H. Für i = 0 haben wir k; i = 1 k/2; i = 2 k/4; i = 3 k/8 und so weiter Deshalb steigt die Summe bis zu lk und die Anzahl der Haufen nimmt um k/(2^i) ab. Die Summe in Gl. 3 sagt uns, dass alle Elemente zwischen den Haufen des aktuellen Laufs verteilt sind. Wie wir gerade herausgefunden haben, ist die Anzahl der Heaps pro Iteration k/(2^i). Aus diesem Grund ist das Maximum für die Meldung pro Warteschlangenlauf n_i = n/(k/(2_i)) = n * (2_i)/k. All dies zusammen erklärt die Gl. 2 und nach dem Löschen der Konstanten erhalten wir die Gleichung auf der rechten Seite.