Priority Queues: Komplexität

Priority Queues könnten z.B. mit den folgenden Datenstrukturen realisiert werden:

1. einer doppelt verketteten Liste (siehe Programmieraufgabe)
2. einem absteigend sortierten Array. Dieses Array soll keine Lücken aufweisen, das Element mit der höchsten Priorität soll sich immer an Position 0 befinden.
3. einem Array in Form eines Max-Heaps.

Beschreiben Sie für 2. und 3. jeweils wie die Methoden add() und pop() implementiert würden. Gegeben eine Queue mit n Elementen, geben Sie dann für alle 3 Implementierungen die Komplexität von add() und pop() im Best Case und Worst Case an und begründen Sie.