{"id":29001,"date":"2022-04-20T17:05:19","date_gmt":"2022-04-20T15:05:19","guid":{"rendered":"https:\/\/www.happycoders.eu\/?p=29001"},"modified":"2024-11-27T15:01:17","modified_gmt":"2024-11-27T14:01:17","slug":"priorityqueue-java","status":"publish","type":"post","link":"https:\/\/www.happycoders.eu\/de\/algorithmen\/priorityqueue-java\/","title":{"rendered":"PriorityQueue in Java (mit Beispiel)"},"content":{"rendered":"\n

In diesem Teil der Tutorialserie stelle ich dir eine Queue vor, die streng genommen gar keine Queue ist: die PriorityQueue<\/code>.<\/p>\n\n\n\n

Wir befinden uns hier in der Klassenhierarchie:<\/p>\n\n\n

\n
\"PriorityQueue
PriorityQueue in der Klassenhierarchie<\/figcaption><\/figure>\n<\/div>\n\n\n

Was ist eine Priority Queue?<\/h2>\n\n\n\n

Eine Priority Queue (deutsch: Vorrangwarteschlange) ist keine Queue im klassischen Sinne. Denn die Elemente werden nicht in FIFO-Reihenfolge entnommen, sondern entsprechend ihrer Priorit\u00e4t. Es wird immer das Element mit der h\u00f6chsten Priorit\u00e4t zuerst entnommen \u2013 unabh\u00e4ngig davon, wann es in die Queue eingef\u00fcgt wurde.<\/p>\n\n\n\n

Das folgende Beispiel zeigt eine Priority Queue mit Elementen der Priorit\u00e4t 10 (h\u00f6chste Priorit\u00e4t), 20, usw. bis 80 (niedrigste Priorit\u00e4t). Ein weiteres Element mit Priorit\u00e4t 45 wird in die Queue eingef\u00fcgt. Die Queue sorgt dann automatisch daf\u00fcr, dass dieses Element nach dem Element mit der Priorit\u00e4t 40 und vor dem Element mit der Priorit\u00e4t 50 entnommen wird.<\/p>\n\n\n

\n
\"Einf\u00fcgen
Einf\u00fcgen eines Elements in eine PriorityQueue<\/figcaption><\/figure>\n<\/div>\n\n\n

Mit welcher Datenstruktur wird eine Priority Queue implementiert? <\/h3>\n\n\n\n

Priority Queues werden in der Regel mit einem Heap<\/a> implementiert.<\/p>\n\n\n\n

Im letzten Teil dieser Tutorialserie werde ich dir zeigen, wie du selbst eine Priority Queue mit einem Heap implementieren kannst.<\/p>\n\n\n\n

Eigenschaften der Java-PriorityQueue <\/h2>\n\n\n\n

Bei der Klasse java.util.PriorityQueue<\/code> ergibt sich die Dequeue-Reihenfolge entweder aus der nat\u00fcrlichen Ordnung\u00b9 der Elemente oder entsprechend eines dem Constructor \u00fcbergebenen Comparators\u00b9. Die zugrundeliegende Datenstruktur ist ein Min-Heap, d. h. am Kopf der Queue befindet sich immer das kleinste Element.<\/p>\n\n\n\n

Die Sortierung ist dabei nicht stabil, d. h. zwei Elemente, die entsprechend der Sortierreihenfolge an gleicher Position stehen, werden nicht zwangsl\u00e4ufig in derselben Reihenfolge entnommen, wie sie in die Queue eingef\u00fcgt wurden.<\/p>\n\n\n\n

PriorityQueue<\/code> ist weder threadsicher noch blockierend. Als threadsicheres, blockierendes Pendant gibt es die PriorityBlockingQueue<\/a>.<\/p>\n\n\n\n

Die Queue-Eigenschaften sind:<\/p>\n\n\n\n

Unterliegende Datenstruktur<\/th>Thread-safe?<\/th>Blocking\/
Non-blocking<\/th>		Bounded\/
Unbounded<\/th>		Iterator Type<\/th><\/tr><\/thead>
Min-Heap
(gespeichert in einem Array)<\/span><\/td>		Nein<\/td>Non-blocking<\/td>Unbounded<\/td>Fail-fast\u00b2<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n

Die PriorityQueue<\/code> verst\u00f6\u00dft \u00fcbrigens nicht<\/em> gegen das Liskovsche Substitutionsprinzip<\/a> (Liskov substitution principle, LSP). Denn die Dokumentation des Queue<\/code>-Interfaces besagt: \"Queues typically, but do not necessarily<\/em>, order elements in a FIFO (first-in-first-out) manner.\"<\/p>\n\n\n\n

\u00b9 Alles \u00fcber die \"nat\u00fcrliche Ordnung\" von Objekten und die Sortierung per Comparator liest du im Artikel \"Vergleichen von Objekten in Java<\/a>\".<\/p>\n\n\n\n

\u00b2 Fail-fast: Der Iterator wirft eine ConcurrentModificationException<\/code>, wenn w\u00e4hrend der Iteration Elemente in die Queue eingef\u00fcgt oder aus dieser entnommen werden.<\/p>\n\n\n\n

Einsatzempfehlung<\/h3>\n\n\n\n

Die PriorityQueue<\/code> kann genau dann eingesetzt werden, wenn eine nicht threadsichere Queue mit oben beschriebener Dequeue-Reihenfolge ben\u00f6tigt wird.<\/p>\n\n\n\n

Allerdings ist zu beachten, dass die PriorityQueue<\/code> im JDK nur an sehr wenigen Stellen eingesetzt wird und somit eine gewisse Wahrscheinlichkeit f\u00fcr das Vorhandensein von Bugs existiert (was wenig genutzt wird, wird auch wenig getestet).<\/p>\n\n\n\n

PriorityQueue Beispiel<\/h2>\n\n\n\n

Das folgende Beispiel zeigt, wie in Java eine Priority Queue erstellt wird und wie mehrere Zufallszahlen in die Queue geschrieben und dann wieder entnommen werden (\u2192 Code auf GitHub<\/a>).<\/p>\n\n\n\n

Wir geben keinen Comparator an, d. h. die Integer<\/code>-Elemente werden entsprechend ihrer nat\u00fcrlichen Ordnung sortiert.<\/p>\n\n\n

public<\/span> class<\/span> PriorityQueueExample<\/span> <\/span>{\n  public<\/span> static<\/span> void<\/span> main<\/span>(String[] args)<\/span> <\/span>{\n    Queue<Integer> queue = new<\/span> PriorityQueue<>();\n\n    \/\/ Enqueue random numbers<\/span>\n    for<\/span> (int<\/span> i = 0<\/span>; i < 8<\/span>; i++) {\n      int<\/span> element = ThreadLocalRandom.current().nextInt(100<\/span>);\n      queue.offer(element);\n      System.out.printf(\"queue.offer(%2d)    -->  queue = %s%n\"<\/span>, element, queue);\n    }\n\n    \/\/ Dequeue all elements<\/span>\n    while<\/span> (!queue.isEmpty()) {\n      Integer element = queue.poll();\n      System.out.printf(\"queue.poll() = %2d  -->  queue = %s%n\"<\/span>, element, queue);\n    }\n  }\n}<\/code><\/span>Code-Sprache:<\/span> Java<\/span> (<\/span>java<\/span>)<\/span><\/small><\/pre>\n\n\n
Es folgt eine beispielhafte Ausgabe des Programms.<\/p>\n\n\n
queue.offer(80)    -->  queue = [80]\nqueue.offer(14)    -->  queue = [14, 80]\nqueue.offer(10)    -->  queue = [10, 80, 14]\nqueue.offer(50)    -->  queue = [10, 50, 14, 80]\nqueue.offer( 9)    -->  queue = [9, 10, 14, 80, 50]\nqueue.offer(58)    -->  queue = [9, 10, 14, 80, 50, 58]\nqueue.offer(41)    -->  queue = [9, 10, 14, 80, 50, 58, 41]\nqueue.offer( 1)    -->  queue = [1, 9, 14, 10, 50, 58, 41, 80]\nqueue.poll() =  1  -->  queue = [9, 10, 14, 80, 50, 58, 41]\nqueue.poll() =  9  -->  queue = [10, 41, 14, 80, 50, 58]\nqueue.poll() = 10  -->  queue = [14, 41, 58, 80, 50]\nqueue.poll() = 14  -->  queue = [41, 50, 58, 80]\nqueue.poll() = 41  -->  queue = [50, 80, 58]\nqueue.poll() = 50  -->  queue = [58, 80]\nqueue.poll() = 58  -->  queue = [80]\nqueue.poll() = 80  -->  queue = []<\/code><\/span>Code-Sprache:<\/span> Klartext<\/span> (<\/span>plaintext<\/span>)<\/span><\/small><\/pre>\n\n\n
Es ist gut zu sehen:<\/p>\n\n\n\n