Komplexität der Einfügung in die Prioritätswarteschlange

Question

Betrachten Sie den folgenden Code, der die ersten beiden Elemente aus der Prioritätswarteschlange aufruft, sie hinzufügt und die Summe zurück in die Prioritätswarteschlange einfügt.

Es ist bekannt, dass das Einfügen in die Prioritätswarteschlange für n Elemente die O (nlogn) -Operation ist. Aber sagen wir, die Prioritätswarteschlange ist als ein Array implementiert. Wird es nicht O (N * N) Operation. Oder was wird die Komplexität für den obigen Code für n Elemente sein.

Answer 1

Eine gut implementierte Prioritätswarteschlange fügt Elemente in O (log n) amortisierten Schritten pro Einfügung ein. Eine gut implementierte Prioritätswarteschlange verwendet sehr wahrscheinlich ein Array, wobei die Array-Elemente gemäß dem heapsort-Algorithmus angeordnet sind.