Prioritätswarteschlange mit Stapel

Question

kann eine Prioritätswarteschlange mit Stapeln erstellen, so dass die Prioritätswarteschlange für jeden Betrieb dieselbe Komplexität hat. Könnte es getan werden?Wenn das so ist, wie?Wenn nicht, was ist die beste Lösung, die getan werden kann?

Jeder Betrieb eines Stapels mit einem Array ist $ O (1) $ , während fast alle Vorgänge der Prioritätswarteschlange ist>$ O (logn) $ . Eine Implementierung kann mit $ 2D $ Stapel erfolgen, wobei jedes Element des Stapels wieder ein Stapel ist. Wenn das erste Element des Hauptstapels das erste Element der anderen Stapel ist. Der Dequeue-Betrieb dauert $ o (n) $ , da es sich um LIFE handelt, und die Prioritätswarteschlange ist FIFO.

Answer 1

Denken Sie darüber nach.Sie können ein Array sortieren, indem Sie alle Elemente in eine Prioritätswarteschlange hinzufügen, und dann die Elemente in sortierter Reihenfolge entfernen.

Wenn Sie in konstanter Zeit eine Prioritätswarteschlange ausführen können, können Sie lineare Zeit sortieren.Aber du kannst nicht.