Mögliche Funktion binärer Heap-Extrakt max O (1)

Ich brauche Hilfe bei der Ermittlung der möglichen Funktion für einen maximalen Heap, damit der Extrakt max in der amortisierten Zeit von ist. Ich sollte hinzufügen, dass ich die mögliche Methode nicht gut verstehe.$O(1)$

Ich weiß, dass die Einfügefunktion mehr "zahlen" sollte, um die Kosten der Extraktion zu senken, und dies muss in Bezug auf die Höhe des Haufens erfolgen (wenn die Höhe des Heap sollte die Einfügung 2 \ log (n) oder \ sum_ {k = 1} ^ n 2 \ log (k) sein )$\lfloor \log(n) \rfloor$$2\log(n)$$\sum_{k=1}^n 2\log(k)$

Versuche Folgendes:

Das Gewicht $w_i$ eines Elements $i$ im Heap $H$ ist seine Tiefe im entsprechenden Binärbaum. Das Element in der Wurzel hat also das Gewicht Null, seine beiden Kinder haben das Gewicht 1 und so weiter. Die definieren Sie als mögliche Funktion

Lassen Sie uns nun die Heap-Operationen analysieren. Zum Einfügen fügen Sie ein neues Element hinzu und fügen höchstens die Tiefe . Dies erhöht das Potential um und kann in -Zeit erfolgen. Dann "sprudeln" Sie das neue Heap-Element, um die Heap-Eigenschaft sicherzustellen. Dies dauert und lässt unverändert. Somit betragen die Kosten für das Einfügen .$d$$\log(n)$$2d$$O(1)$$O(\log n)$$\Phi(H)$$O(\log(n)+\Delta(\Phi(H)))=O(\log n)$

Betrachten Sie nun den extractMin . Sie nehmen die Wurzel heraus und ersetzen sie durch das letzte Element im Heap. Dies verringert das Potenzial um , sodass Sie es sich leisten können, die Heap-Eigenschaft zu reparieren, und daher betragen die amortisierten Kosten jetzt .$2\log(n)$$O(1)$

Wenn Sie eine allgemeine Frage zur möglichen Funktion haben, sollten Sie diese als eine andere Frage stellen.