Prioritätswarteschlangen können mithilfe von Heaps implementiert werden. Eine gewöhnliche Warteschlange ist eine First-In-First-Out-Datenstruktur. Elemente werden an das Ende der Warteschlange angehängt und vom Anfang entfernt. In einer Prioritätswarteschlange werden Elementen Prioritäten zugewiesen. Beim Zugriff auf Elemente wird zuerst das Element mit der höchsten Priorität entfernt. Beispielsweise weist die Notaufnahme eines Krankenhauses den Patienten Prioritätsnummern zu; Der Patient mit der höchsten Priorität wird zuerst behandelt.

Eine Prioritätswarteschlange kann mithilfe eines Heaps implementiert werden, bei dem der Stamm das Objekt mit der höchsten Priorität in der Warteschlange ist. Heaps wurden in Heap Sort eingeführt. Das Klassendiagramm für die Prioritätswarteschlange ist in der folgenden Abbildung dargestellt. Seine Implementierung ist im folgenden Code angegeben.

Der folgende Code zeigt ein Beispiel für die Verwendung einer Prioritätswarteschlange für Patienten. Die Klasse Patient wird in den Zeilen 21–38 definiert. In den Zeilen 6–9 werden vier Patienten mit zugehörigen Prioritätswerten angelegt. Zeile 8 erstellt eine Prioritätswarteschlange. Die Patienten werden in den Zeilen 12–15 eingereiht. Zeile 18 entfernt einen Patienten aus der Warteschlange.

Cindy(Priorität:7) Tim(Priorität:5) John(Priorität:2) Jim(Priorität:1)