{"id":29914,"date":"2022-05-16T17:23:00","date_gmt":"2022-05-16T15:23:00","guid":{"rendered":"https:\/\/www.happycoders.eu\/?p=29914"},"modified":"2024-11-27T15:02:00","modified_gmt":"2024-11-27T14:02:00","slug":"priority-queue-implementieren-heap","status":"publish","type":"post","link":"https:\/\/www.happycoders.eu\/de\/algorithmen\/priority-queue-implementieren-heap\/","title":{"rendered":"Priority Queue mit einem Heap implementieren"},"content":{"rendered":"\n<p>Im vorherigen Teil der Tutorialserie haben wir eine <a href=\"\/de\/algorithmen\/queue-implementieren-array\/\">Queue mit einem Array implementiert<\/a>. In diesem letzten Teil der Serie zeige ich dir, wie du eine Priority Queue implementierst \u2013 und zwar mit Hilfe eines Heaps.<\/p>\n\n\n\n<p>Zur Erinnerung: Bei einer <a href=\"\/de\/algorithmen\/priorityqueue-java\/\">Priority Queue<\/a> werden die Elemente nicht in FIFO-Reihenfolge entnommen, sondern entsprechend ihrer Priorit\u00e4t. Das Element mit der h\u00f6chsten Priorit\u00e4t steht immer am Kopf der Queue und wird zuerst entnommen \u2013 unabh\u00e4ngig davon, wann es in die Queue eingef\u00fcgt wurde.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"was-ist-ein-heap\">Was ist ein Heap?<\/h2>\n\n\n\n<p>Ein \"Heap\" ist einen <a href=\"https:\/\/www.happycoders.eu\/de\/algorithmen\/binaerbaum-java\/\">Bin\u00e4rbaum<\/a>, in dem jeder Knoten entweder gr\u00f6\u00dfer\/gleich seiner Kinder ist (\"Max Heap\") \u2013 oder kleiner\/gleich seiner Kinder (\"Min-Heap\").<\/p>\n\n\n\n<p>F\u00fcr die Priority Queue in diesem Artikel verwenden wir einen <em>Min<\/em>-Heap, da die h\u00f6chste Priorit\u00e4t diejenige mit der niedrigsten Zahl ist (Prio 1 ist in der Regel h\u00f6her als Prio 2).<\/p>\n\n\n\n<p>Hier ist ein Beispiel, wie so ein Min-Heap aussehen k\u00f6nnte:<\/p>\n\n\n\n<div class=\"wp-block-image\"><figure class=\"aligncenter size-half_400\"><img decoding=\"async\" width=\"400\" height=\"204\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-with-min-heap-example-400x204.png\" alt=\"Min-Heap-Beispiel\" class=\"wp-image-29925\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-with-min-heap-example-400x204.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-with-min-heap-example-224x114.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-with-min-heap-example-336x171.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-with-min-heap-example-504x257.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-with-min-heap-example-672x343.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-with-min-heap-example-600x306.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-with-min-heap-example.png 800w\" sizes=\"(max-width: 400px) 100vw, 400px\" \/><figcaption>Min-Heap-Beispiel<\/figcaption><\/figure><\/div>\n\n\n\n<p>Das Element an jedem Knoten dieses Baums ist kleiner als die Elemente seiner beiden Kindknoten: <\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>1 ist kleiner als 2 und 4;<\/li><li>2 ist kleiner als 3 und 7;<\/li><li>4 ist kleiner als 9 und 6;<\/li><li>3 ist kleiner als 8 und 5.<\/li><\/ul>\n\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"array-darstellung-eines-heaps\">Array-Darstellung eines Heaps<\/h3>\n\n\n\n<p>Ein Heap k\u00f6nnen wir in einem Array speichern, indem wir dessen Elemente zeilenweise \u2013 von links oben nach rechts unten \u2013 auf das Array abbilden:<\/p>\n\n\n\n<div class=\"wp-block-image\"><figure class=\"aligncenter size-half_400\"><img decoding=\"async\" width=\"400\" height=\"228\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/mapping-a-min-heap-to-an-array-400x228.png\" alt=\"Abbildung eines Min-Heaps auf ein Array\" class=\"wp-image-29927\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/mapping-a-min-heap-to-an-array-400x228.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/mapping-a-min-heap-to-an-array-224x128.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/mapping-a-min-heap-to-an-array-336x192.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/mapping-a-min-heap-to-an-array-504x287.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/mapping-a-min-heap-to-an-array-672x383.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/mapping-a-min-heap-to-an-array-600x342.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/mapping-a-min-heap-to-an-array.png 800w\" sizes=\"(max-width: 400px) 100vw, 400px\" \/><figcaption>Abbildung eines Min-Heaps auf ein Array<\/figcaption><\/figure><\/div>\n\n\n\n<p>Unser Beispiel-Heap sieht als Array wie folgt aus:<\/p>\n\n\n\n<div class=\"wp-block-image\"><figure class=\"aligncenter size-half_400\"><img decoding=\"async\" width=\"400\" height=\"31\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/min-heap-mapped-to-an-array-400x31.png\" alt=\"Array-Repr\u00e4sentation des Min-Heaps\" class=\"wp-image-29928\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/min-heap-mapped-to-an-array-400x31.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/min-heap-mapped-to-an-array-224x17.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/min-heap-mapped-to-an-array-336x26.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/min-heap-mapped-to-an-array-504x39.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/min-heap-mapped-to-an-array-672x52.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/min-heap-mapped-to-an-array-600x47.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/min-heap-mapped-to-an-array.png 800w\" sizes=\"(max-width: 400px) 100vw, 400px\" \/><figcaption>Array-Repr\u00e4sentation des Min-Heaps<\/figcaption><\/figure><\/div>\n\n\n\n<p>Bei einem Min-Heap ist das kleinste Element immer oben, im Array also immer an erster Position. Genau deshalb siehst du, wenn du eine Java-<code>PriorityQueue<\/code> als String ausgibst, immer das kleinste Element links. Was du siehst, ist die Array-Darstellung des der <code>PriorityQueue<\/code> zugrunde liegenden Min-Heaps.<\/p>\n\n\n\n<p>Mit den folgenden Codezeilen l\u00e4sst sich das gut demonstrieren:<\/p>\n\n\n<pre class=\"wp-block-code\" aria-describedby=\"shcb-language-2\" data-shcb-language-name=\"Java\" data-shcb-language-slug=\"java\"><span><code class=\"hljs language-java\">PriorityQueue&lt;Integer&gt; priorityQueue = <span class=\"hljs-keyword\">new<\/span> PriorityQueue&lt;&gt;();\npriorityQueue.addAll(List.of(<span class=\"hljs-number\">4<\/span>, <span class=\"hljs-number\">7<\/span>, <span class=\"hljs-number\">3<\/span>, <span class=\"hljs-number\">8<\/span>, <span class=\"hljs-number\">2<\/span>, <span class=\"hljs-number\">9<\/span>, <span class=\"hljs-number\">6<\/span>, <span class=\"hljs-number\">5<\/span>, <span class=\"hljs-number\">1<\/span>));\nSystem.out.println(<span class=\"hljs-string\">\"priorityQueue = \"<\/span> + priorityQueue);\n<\/code><\/span><small class=\"shcb-language\" id=\"shcb-language-2\"><span class=\"shcb-language__label\">Code-Sprache:<\/span> <span class=\"shcb-language__name\">Java<\/span> <span class=\"shcb-language__paren\">(<\/span><span class=\"shcb-language__slug\">java<\/span><span class=\"shcb-language__paren\">)<\/span><\/small><\/pre>\n\n\n<p>Das Ausgabe des Programms lautet:<\/p>\n\n\n<pre class=\"wp-block-code\" aria-describedby=\"shcb-language-3\" data-shcb-language-name=\"Klartext\" data-shcb-language-slug=\"plaintext\"><span><code class=\"hljs language-plaintext\">priorityQueue = &#091;1, 2, 4, 3, 7, 9, 6, 8, 5]\n<\/code><\/span><small class=\"shcb-language\" id=\"shcb-language-3\"><span class=\"shcb-language__label\">Code-Sprache:<\/span> <span class=\"shcb-language__name\">Klartext<\/span> <span class=\"shcb-language__paren\">(<\/span><span class=\"shcb-language__slug\">plaintext<\/span><span class=\"shcb-language__paren\">)<\/span><\/small><\/pre>\n\n\n<p>Das kleinste Element ist ganz links. Und wenn du genau hinschaust, erkennst du, dass die Zahlen exakt die gleiche Reihenfolge haben wie in der grafischen Array-Darstellung oben. Der Min-Heap der im Beispiel erstellten <code>PriorityQueue<\/code> ist genau der, den ich zu Beginn des Artikels abgebildet habe.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"priority-queue-mit-einem-min-heap-der-algorithmus\">Priority Queue mit einem Min-Heap \u2013 Der Algorithmus<\/h2>\n\n\n\n<p>OK, das kleinste Element steht immer ganz links. Damit ist schon mal klar, wie die <code>peek()<\/code>-Operation zu funktionieren hat: sie muss einfach das erste Element des Arrays zur\u00fcckgeben.<\/p>\n\n\n\n<p>Doch wie wird so ein Heap aufgebaut? Wie funktionieren <code>enqueue()<\/code> und <code>dequeue()<\/code>?<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"einfuegen-in-den-min-heap-sift-up\">Einf\u00fcgen in den Min-Heap: Sift Up<\/h3>\n\n\n\n<p>Um ein Element in einen Heap einzuf\u00fcgen, gehen wir wie folgt vor:<\/p>\n\n\n\n<ol class=\"wp-block-list\"><li>Wir f\u00fcgen das neue Element als letztes Element in den Baums ein, d. h.:<ul><li>Ist der Baum leer, f\u00fcgen wir das neue Element als Wurzel ein.<\/li><li>Wenn die unterste Ebene des Baums nicht voll ist, f\u00fcgen wir das neue Element neben dem letzen Knoten der untersten Ebene ein.<\/li><li>Ist die unterste Ebene voll, dann h\u00e4ngen wir den Knoten unter den ersten Knoten der untersten Ebene.<\/li><\/ul><\/li><li>Solange der Elternknoten des neuen Elements kleiner ist als das Element selbst (was die Min-Heap Regel verletzten w\u00fcrde), vertauschen wir den neuen Knoten mit seinem Elternknoten.<\/li><\/ol>\n\n\n\n<p>Schritt 1 h\u00f6rt sich kompliziert an, bedeutet in der Array-Darstellung aber lediglich, dass das neue Element an die erste freie Stelle des Arrays gesetzt wird. Schritt 2 sorgt daf\u00fcr, dass am Ende der Operation wieder jedes Element kleiner ist als seine Kinder.<\/p>\n\n\n\n<p>Das Beispiel im folgenden Abschnitt demonstriert die beiden Schritte.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"einfuegen-in-den-min-heap-beispiel\">Einf\u00fcgen in den Min-Heap: Beispiel<\/h3>\n\n\n\n<p>An den folgenden Beispielen zeige ich dir Schritt f\u00fcr Schritt, wie eine auf einem Min-Heap basierende Priority Queue mit den oben gezeigten Beispielwerten (4, 7, 3, 8, 2, 9, 6, 5, 1) gef\u00fcllt wird. In jedem Schritt zeige ich den Min-Heap jeweils in Baum- und in Array-Darstellung.<\/p>\n\n\n\n<h4 class=\"wp-block-heading\">1. Element \u2013 Einf\u00fcgen der 4 in eine leere Priority Queue<\/h4>\n\n\n\n<p>Das erste einzuf\u00fcgende Element wird zum Wurzelknoten des Baumes; im Array wird es an die erste Position gesetzt:<\/p>\n\n\n\n<div class=\"wp-block-image\"><figure class=\"aligncenter size-half_400\"><img decoding=\"async\" width=\"400\" height=\"107\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-enqueue-4-400x107.png\" alt=\"Priority Queue \/ Min-Heap mit Wurzelknoten 4\" class=\"wp-image-29934\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-enqueue-4-400x107.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-enqueue-4-224x60.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-enqueue-4-336x90.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-enqueue-4-504x135.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-enqueue-4-672x180.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-enqueue-4-600x161.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-enqueue-4.png 800w\" sizes=\"(max-width: 400px) 100vw, 400px\" \/><\/figure><\/div>\n\n\n\n<h4 class=\"wp-block-heading\">2. Element \u2013 Einf\u00fcgen der 7<\/h4>\n\n\n\n<p>Die 7 wird unter den ersten Knoten der untersten Ebene eingeh\u00e4ngt \u2013 also links unter die Wurzel. Im Array wird sie einfach angeh\u00e4ngt:<\/p>\n\n\n\n<div class=\"wp-block-image\"><figure class=\"aligncenter size-half_400\"><img decoding=\"async\" width=\"400\" height=\"145\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-enqueue-7-400x145.png\" alt=\"Priority Queue \/ Min-Heap mit 4 und 7\" class=\"wp-image-29935\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-enqueue-7-400x145.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-enqueue-7-224x81.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-enqueue-7-336x122.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-enqueue-7-504x183.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-enqueue-7-672x244.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-enqueue-7-600x218.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-enqueue-7.png 800w\" sizes=\"(max-width: 400px) 100vw, 400px\" \/><\/figure><\/div>\n\n\n\n<p>Die 7 ist gr\u00f6\u00dfer als ihr Elternknoten 4 \u2013 damit ist die Einf\u00fcgeoperation abgeschlossen. Das kleinste Element steht nach wie vor am Anfang der Priority Queue.<\/p>\n\n\n\n<h4 class=\"wp-block-heading\">3. Element - Einf\u00fcgen der 3<\/h4>\n\n\n\n<p>Die 3 wird neben dem letzten Knoten der untersten Ebene, also rechts unter der 4, angeh\u00e4ngt. Im Array kommt sie ans Ende:<\/p>\n\n\n\n<div class=\"wp-block-image\"><figure class=\"aligncenter size-half_400\"><img decoding=\"async\" width=\"400\" height=\"145\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-enqueue-3-step1-400x145.png\" alt=\"Priority Queue \/ Min-Heap mit 4, 7 und 3\" class=\"wp-image-29936\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-enqueue-3-step1-400x145.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-enqueue-3-step1-224x81.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-enqueue-3-step1-336x122.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-enqueue-3-step1-504x183.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-enqueue-3-step1-672x244.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-enqueue-3-step1-600x218.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-enqueue-3-step1.png 800w\" sizes=\"(max-width: 400px) 100vw, 400px\" \/><\/figure><\/div>\n\n\n\n<p>Die 3 ist kleiner als ihr Elternknoten. Die Regeln des Min-Heaps sind also verletzt. Wir stellen den Min-Heap wieder her, in dem wir die 3 mit der 4 tauschen:<\/p>\n\n\n\n<div class=\"wp-block-image\"><figure class=\"aligncenter size-full_800\"><img decoding=\"async\" width=\"800\" height=\"170\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-enqueue-3-step2-siftUp-800x170.png\" alt=\"Priority Queue \/ Min-Heap mit 4, 7 und 3: Tausch der 3 und 4\" class=\"wp-image-29937\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-enqueue-3-step2-siftUp-800x170.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-enqueue-3-step2-siftUp-224x48.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-enqueue-3-step2-siftUp-336x71.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-enqueue-3-step2-siftUp-504x107.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-enqueue-3-step2-siftUp-672x143.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-enqueue-3-step2-siftUp-400x85.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-enqueue-3-step2-siftUp-600x128.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-enqueue-3-step2-siftUp-944x201.png 944w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-enqueue-3-step2-siftUp-1200x255.png 1200w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-enqueue-3-step2-siftUp.png 1600w\" sizes=\"(max-width: 800px) 100vw, 800px\" \/><\/figure><\/div>\n\n\n\n<p>Damit haben wir wieder einen validen Min-Heap.<\/p>\n\n\n\n<p>Wir \u00fcberspringen die 8, 2, 9, 6 und 5 (diese werden analog eingef\u00fcgt) und kommen zum...<\/p>\n\n\n\n<h4 class=\"wp-block-heading\">9. Element \u2013 Einf\u00fcgen der 1<\/h4>\n\n\n\n<p>Zuletzt f\u00fcgen wir die 1 am Ende der Queue (und des Arrays) ein:<\/p>\n\n\n\n<div class=\"wp-block-image\"><figure class=\"aligncenter size-half_400\"><img decoding=\"async\" width=\"400\" height=\"258\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-enqueue-1-step1-400x258.png\" alt=\"Priority Queue \/ Min-Heap mit eingef\u00fcgter 1\" class=\"wp-image-29938\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-enqueue-1-step1-400x258.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-enqueue-1-step1-224x144.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-enqueue-1-step1-336x217.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-enqueue-1-step1-504x325.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-enqueue-1-step1-672x433.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-enqueue-1-step1-600x387.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-enqueue-1-step1.png 800w\" sizes=\"(max-width: 400px) 100vw, 400px\" \/><\/figure><\/div>\n\n\n\n<p>Die 1 ist gr\u00f6\u00dfer als ihr Elternknoten 5; unser Baum ist also kein g\u00fcltiger Min-Heap mehr. Um ihn zu reparieren, tauschen wir zun\u00e4chst die 1 mit der 5:<\/p>\n\n\n\n<div class=\"wp-block-image\"><figure class=\"aligncenter size-full_800\"><img decoding=\"async\" width=\"800\" height=\"284\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-enqueue-1-step2-siftUp-800x284.png\" alt=\"Priority Queue \/ Min-Heap mit eingef\u00fcgter 1: Tausch der 1 und 5\" class=\"wp-image-29940\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-enqueue-1-step2-siftUp-800x284.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-enqueue-1-step2-siftUp-224x80.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-enqueue-1-step2-siftUp-336x119.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-enqueue-1-step2-siftUp-504x179.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-enqueue-1-step2-siftUp-672x239.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-enqueue-1-step2-siftUp-400x142.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-enqueue-1-step2-siftUp-600x213.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-enqueue-1-step2-siftUp-944x335.png 944w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-enqueue-1-step2-siftUp-1200x426.png 1200w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-enqueue-1-step2-siftUp.png 1600w\" sizes=\"(max-width: 800px) 100vw, 800px\" \/><\/figure><\/div>\n\n\n\n<p>Die 1 ist ebenfalls gr\u00f6\u00dfer als ihr neuer Elternknoten 3; somit tauschen wir erneut:<\/p>\n\n\n\n<div class=\"wp-block-image\"><figure class=\"aligncenter size-full_800\"><img decoding=\"async\" width=\"800\" height=\"284\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-enqueue-1-step3-siftUp2-800x284.png\" alt=\"Priority Queue \/ Min-Heap mit eingef\u00fcgter 1: Tausch der 1 und 3\" class=\"wp-image-29945\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-enqueue-1-step3-siftUp2-800x284.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-enqueue-1-step3-siftUp2-224x80.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-enqueue-1-step3-siftUp2-336x119.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-enqueue-1-step3-siftUp2-504x179.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-enqueue-1-step3-siftUp2-672x239.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-enqueue-1-step3-siftUp2-400x142.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-enqueue-1-step3-siftUp2-600x213.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-enqueue-1-step3-siftUp2-944x335.png 944w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-enqueue-1-step3-siftUp2-1200x426.png 1200w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-enqueue-1-step3-siftUp2.png 1600w\" sizes=\"(max-width: 800px) 100vw, 800px\" \/><\/figure><\/div>\n\n\n\n<p>Die 1 ist auch gr\u00f6\u00dfer als die Wurzel 2, also tauschen wir ein drittes Mal:<\/p>\n\n\n\n<div class=\"wp-block-image\"><figure class=\"aligncenter size-full_800\"><img decoding=\"async\" width=\"800\" height=\"284\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-enqueue-1-step4-siftUp-800x284.png\" alt=\"Priority Queue \/ Min-Heap mit eingef\u00fcgter 1: Tausch der 1 und 2\" class=\"wp-image-29942\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-enqueue-1-step4-siftUp-800x284.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-enqueue-1-step4-siftUp-224x80.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-enqueue-1-step4-siftUp-336x119.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-enqueue-1-step4-siftUp-504x179.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-enqueue-1-step4-siftUp-672x239.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-enqueue-1-step4-siftUp-400x142.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-enqueue-1-step4-siftUp-600x213.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-enqueue-1-step4-siftUp-944x335.png 944w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-enqueue-1-step4-siftUp-1200x426.png 1200w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-enqueue-1-step4-siftUp.png 1600w\" sizes=\"(max-width: 800px) 100vw, 800px\" \/><\/figure><\/div>\n\n\n\n<p>Da die 1 nun an der Wurzel angelangt ist, ist die Operation beendet. Der Baum ist wieder ein Min-Heap. Das kleinste Element steht an der Wurzel des Baumes (und am Anfang des Arrays).<\/p>\n\n\n\n<p>Dieses Hochreichen des eingef\u00fcgten Elements auf die eben gezeigte Weise bezeichnet man als \"Sift Up\". <\/p>\n\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"vereinfachter-sift-up-algorithmus\">Vereinfachter Sift-Up-Algorithmus<\/h3>\n\n\n\n<p>Tats\u00e4chlich brauchen wir uns gar nicht die M\u00fche zu machen das neue Element am Ende einzuf\u00fcgen, um es dann schrittweise mit seinem Elternknoten zu tauschen. Stattdessen k\u00f6nnen wir uns das neue Element merken, die gr\u00f6\u00dferen Elternelemente nach unten schieben und zum Schluss das neue Element direkt an seine Zielposition setzen.<\/p>\n\n\n\n<p>Die folgenden Grafiken zeigen das Einf\u00fcgen der 1 nach dem vereinfachten Algorithmus.<\/p>\n\n\n\n<p>Die 1 ist kleiner als der Elternknoten des freien Knotens. Wir schieben daher die 5 in den freien Knoten:<\/p>\n\n\n\n<div class=\"wp-block-image\"><figure class=\"aligncenter size-full_800\"><img decoding=\"async\" width=\"800\" height=\"284\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-simple-siftUp-1-800x284.png\" alt=\"Vereinfachter siftUp-Algoriothmus: Verschieben der 5\" class=\"wp-image-29948\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-simple-siftUp-1-800x284.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-simple-siftUp-1-224x80.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-simple-siftUp-1-336x119.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-simple-siftUp-1-504x179.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-simple-siftUp-1-672x239.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-simple-siftUp-1-400x142.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-simple-siftUp-1-600x213.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-simple-siftUp-1-944x335.png 944w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-simple-siftUp-1-1200x426.png 1200w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-simple-siftUp-1.png 1600w\" sizes=\"(max-width: 800px) 100vw, 800px\" \/><\/figure><\/div>\n\n\n\n<p>Die einzuf\u00fcgende 1 ist ebenso kleiner als die 3; wir schieben die 3 nach unten:<\/p>\n\n\n\n<div class=\"wp-block-image\"><figure class=\"aligncenter size-full_800\"><img decoding=\"async\" width=\"800\" height=\"284\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-simple-siftUp-2-800x284.png\" alt=\"Vereinfachter siftUp-Algoriothmus: Verschieben der 3\" class=\"wp-image-29949\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-simple-siftUp-2-800x284.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-simple-siftUp-2-224x80.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-simple-siftUp-2-336x119.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-simple-siftUp-2-504x179.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-simple-siftUp-2-672x239.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-simple-siftUp-2-400x142.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-simple-siftUp-2-600x213.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-simple-siftUp-2-944x335.png 944w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-simple-siftUp-2-1200x426.png 1200w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-simple-siftUp-2.png 1600w\" sizes=\"(max-width: 800px) 100vw, 800px\" \/><\/figure><\/div>\n\n\n\n<p>Die 1 ist kleiner als die 2; wir schieben auch die 2 nach unten:<\/p>\n\n\n\n<div class=\"wp-block-image\"><figure class=\"aligncenter size-full_800\"><img decoding=\"async\" width=\"800\" height=\"284\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-simple-siftUp-3-800x284.png\" alt=\"Vereinfachter siftUp-Algoriothmus: Verschieben der 2\" class=\"wp-image-29950\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-simple-siftUp-3-800x284.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-simple-siftUp-3-224x80.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-simple-siftUp-3-336x119.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-simple-siftUp-3-504x179.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-simple-siftUp-3-672x239.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-simple-siftUp-3-400x142.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-simple-siftUp-3-600x213.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-simple-siftUp-3-944x335.png 944w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-simple-siftUp-3-1200x426.png 1200w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-simple-siftUp-3.png 1600w\" sizes=\"(max-width: 800px) 100vw, 800px\" \/><\/figure><\/div>\n\n\n\n<p>Wir k\u00f6nnen keine weiteren Elemente nach unten schieben und setzen das einzuf\u00fcgende Element, die 1, auf den freigewordenen Wurzelknoten (oder das erste Feld des Arrays):<\/p>\n\n\n\n<div class=\"wp-block-image\"><figure class=\"aligncenter size-half_400\"><img decoding=\"async\" width=\"400\" height=\"258\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-simple-siftUp-4b-400x258.png\" alt=\"Vereinfachter siftUp-Algoriothmus: Setzen der 1\" class=\"wp-image-29967\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-simple-siftUp-4b-400x258.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-simple-siftUp-4b-224x144.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-simple-siftUp-4b-336x217.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-simple-siftUp-4b-504x325.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-simple-siftUp-4b-672x433.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-simple-siftUp-4b-600x387.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-simple-siftUp-4b.png 800w\" sizes=\"(max-width: 400px) 100vw, 400px\" \/><\/figure><\/div>\n\n\n\n<p>Damit ist die Sift-Up-Operation abgeschlossen.<\/p>\n\n\n\n<p>Das Einf\u00fcgen eines Elements in die Priority Queue (bzw. in den Min-Heap) mag beim ersten Durchlesen sehr komplex erscheinen. Falls du es nicht verstanden hast, mach eine kurze Pause und wiederhole das Kapitel noch einmal, bevor du zur Dequeue-Operation fortschreitest.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"entnahme-aus-dem-min-heap-sift-down\">Entnahme aus dem Min-Heap: Sift Down<\/h3>\n\n\n\n<p>Wir wissen, dass das kleinste Element immer an der Wurzel des Baumes steht (oder am Anfang des Arrays).<\/p>\n\n\n\n<p>Um es zu entnehmen, gehen wir wie folgt vor:<\/p>\n\n\n\n<ol class=\"wp-block-list\"><li>Wir entfernen das Wurzelelement aus dem Baum.<\/li><li>Wir verschieben den letzten Knoten der letzten Ebene des Baumes (das entspricht dem letzten Element des Arrays) an die freigewordene Wurzelposition.<\/li><li>Solange dieser Knoten gr\u00f6\u00dfer ist als eines seiner Kinder (was die Min-Heap Regel verletzten w\u00fcrde), vertauschen wir den Knoten mit seinem kleinsten Kindknoten.<\/li><\/ol>\n\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"entnahme-aus-dem-min-heap-beispiel\">Entnahme aus dem Min-Heap: Beispiel<\/h3>\n\n\n\n<p>Das folgende Beispiel zeigt, wie wir das Wurzelelement des im letzten Kapitel gef\u00fcllten Min-Heaps entnehmen und danach die Min-Heap-Bedingung wiederherstellen.<\/p>\n\n\n\n<p>Als erstes entnehmen wir das Wurzelelement:<\/p>\n\n\n\n<div class=\"wp-block-image\"><figure class=\"aligncenter size-full_800\"><img decoding=\"async\" width=\"800\" height=\"258\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-dequeue-1-step-1-800x258.png\" alt=\"Priority Queue \/ Min-Heap: Dequeue: Entnahme Wurzelelement\" class=\"wp-image-29957\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-dequeue-1-step-1-800x258.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-dequeue-1-step-1-224x72.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-dequeue-1-step-1-336x108.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-dequeue-1-step-1-504x163.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-dequeue-1-step-1-672x217.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-dequeue-1-step-1-400x129.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-dequeue-1-step-1-600x194.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-dequeue-1-step-1-944x304.png 944w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-dequeue-1-step-1-1200x387.png 1200w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-dequeue-1-step-1.png 1600w\" sizes=\"(max-width: 800px) 100vw, 800px\" \/><\/figure><\/div>\n\n\n\n<p>Als zweites verschieben wir das letzte Element des Baumes, die 5, an die frei gewordene Wurzel:<\/p>\n\n\n\n<div class=\"wp-block-image\"><figure class=\"aligncenter size-full_800\"><img decoding=\"async\" width=\"800\" height=\"284\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-dequeue-1-step-2-800x284.png\" alt=\"Priority Queue \/ Min-Heap: Dequeue: 5 nach vorne schieben\" class=\"wp-image-29958\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-dequeue-1-step-2-800x284.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-dequeue-1-step-2-224x80.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-dequeue-1-step-2-336x119.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-dequeue-1-step-2-504x179.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-dequeue-1-step-2-672x239.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-dequeue-1-step-2-400x142.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-dequeue-1-step-2-600x213.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-dequeue-1-step-2-944x335.png 944w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-dequeue-1-step-2-1200x426.png 1200w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-dequeue-1-step-2.png 1600w\" sizes=\"(max-width: 800px) 100vw, 800px\" \/><\/figure><\/div>\n\n\n\n<p>Da das neue Wurzelelement, die 5, jetzt gr\u00f6\u00dfer ist als das kleinste seiner Kinder, die 2, vertauschen wir diese beiden Elemente:<\/p>\n\n\n\n<div class=\"wp-block-image\"><figure class=\"aligncenter size-full_800\"><img decoding=\"async\" width=\"800\" height=\"284\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-dequeue-1-step-3-siftDown-1-800x284.png\" alt=\"Priority Queue \/ Min-Heap: Dequeue: Tauschen von 5 und 2\" class=\"wp-image-29959\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-dequeue-1-step-3-siftDown-1-800x284.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-dequeue-1-step-3-siftDown-1-224x80.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-dequeue-1-step-3-siftDown-1-336x119.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-dequeue-1-step-3-siftDown-1-504x179.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-dequeue-1-step-3-siftDown-1-672x239.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-dequeue-1-step-3-siftDown-1-400x142.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-dequeue-1-step-3-siftDown-1-600x213.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-dequeue-1-step-3-siftDown-1-944x335.png 944w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-dequeue-1-step-3-siftDown-1-1200x426.png 1200w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-dequeue-1-step-3-siftDown-1.png 1600w\" sizes=\"(max-width: 800px) 100vw, 800px\" \/><\/figure><\/div>\n\n\n\n<p>Die 5 ist weiterhin gr\u00f6\u00dfer als das kleinste ihrer Kinder, die 3. Wir tauschen ein zweites Mal:<\/p>\n\n\n\n<figure class=\"wp-block-image size-full\"><img decoding=\"async\" width=\"1600\" height=\"568\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-dequeue-1-step-3-siftDown-2.png\" alt=\"Priority Queue \/ Min-Heap: Dequeue: Tauschen von 5 und 3\" class=\"wp-image-29960\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-dequeue-1-step-3-siftDown-2.png 1600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-dequeue-1-step-3-siftDown-2-224x80.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-dequeue-1-step-3-siftDown-2-336x119.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-dequeue-1-step-3-siftDown-2-504x179.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-dequeue-1-step-3-siftDown-2-672x239.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-dequeue-1-step-3-siftDown-2-400x142.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-dequeue-1-step-3-siftDown-2-600x213.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-dequeue-1-step-3-siftDown-2-800x284.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-dequeue-1-step-3-siftDown-2-944x335.png 944w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-dequeue-1-step-3-siftDown-2-1200x426.png 1200w\" sizes=\"(max-width: 1600px) 100vw, 1600px\" \/><\/figure>\n\n\n\n<p>Die 5 ist jetzt gr\u00f6\u00dfer als ihr einziges Kind; die Min-Heap-Bedingung ist damit wiederhergestellt.<\/p>\n\n\n\n<p>An der Wurzel des Min-Heaps (bzw. am Anfang des Arrays) befindet sich jetzt die 2, das neue kleinste Element nach Entnahme der 1.<\/p>\n\n\n\n<p>Das Herunterwandern des an die Wurzel verschobenen Elements bezeichnet man als \"Sift Down\". <\/p>\n\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"vereinfachter-sift-down-algorithmus\">Vereinfachter Sift-Down-Algorithmus<\/h3>\n\n\n\n<p>Auch den Sift-Down-Algorithmus k\u00f6nnen wir vereinfachen. Wir m\u00fcssen das letzte Element (im Beispiel die 5) nicht erst an die Wurzel schieben, um es dann schrittweise mit seinen Kindern zu tauschen. Wir k\u00f6nnen auch zuerst die gr\u00f6\u00dferen Elemente nach oben schieben und am Ende das letzte Element direkt an seine endg\u00fcltige Position verschieben.<\/p>\n\n\n\n<p>Die folgenden Grafiken zeigen das Herunterreichen der 5 (oder besser gesagt: des freien Feldes, auf das am Ende die 5 gesetzt wird) nach dem vereinfachten Algorithmus. <\/p>\n\n\n\n<p>Die 5 ist gr\u00f6\u00dfer als der kleinste Kindknoten der leeren Wurzel, die 2. Wir schieben die 2 nach oben:<\/p>\n\n\n\n<div class=\"wp-block-image\"><figure class=\"aligncenter size-full_800\"><img decoding=\"async\" width=\"800\" height=\"284\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-simple-siftDown-1-800x284.png\" alt=\"Vereinfachter siftDown-Algoriothmus: Verschieben der 2\" class=\"wp-image-29962\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-simple-siftDown-1-800x284.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-simple-siftDown-1-224x80.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-simple-siftDown-1-336x119.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-simple-siftDown-1-504x179.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-simple-siftDown-1-672x239.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-simple-siftDown-1-400x142.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-simple-siftDown-1-600x213.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-simple-siftDown-1-944x335.png 944w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-simple-siftDown-1-1200x426.png 1200w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-simple-siftDown-1.png 1600w\" sizes=\"(max-width: 800px) 100vw, 800px\" \/><\/figure><\/div>\n\n\n\n<p>Die 5 ist ebenso gr\u00f6\u00dfer als das kleinste Kind des jetzt freien Platzes, die 3. Wir schieben auch die 3 nach oben:<\/p>\n\n\n\n<div class=\"wp-block-image\"><figure class=\"aligncenter size-full_800\"><img decoding=\"async\" width=\"800\" height=\"284\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-simple-siftDown-2-800x284.png\" alt=\"Vereinfachter siftDown-Algoriothmus: Verschieben der 3\" class=\"wp-image-29963\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-simple-siftDown-2-800x284.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-simple-siftDown-2-224x80.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-simple-siftDown-2-336x119.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-simple-siftDown-2-504x179.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-simple-siftDown-2-672x239.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-simple-siftDown-2-400x142.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-simple-siftDown-2-600x213.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-simple-siftDown-2-944x335.png 944w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-simple-siftDown-2-1200x426.png 1200w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-simple-siftDown-2.png 1600w\" sizes=\"(max-width: 800px) 100vw, 800px\" \/><\/figure><\/div>\n\n\n\n<p>Die 5 ist <em>nicht<\/em> gr\u00f6\u00dfer als das einzige Kind des jetzt freien Platzes, die 8. Wir haben also das Zielfeld f\u00fcr die 5 gefunden und schieben die 5 dorthin:<\/p>\n\n\n\n<div class=\"wp-block-image\"><figure class=\"aligncenter size-full_800\"><img decoding=\"async\" width=\"800\" height=\"284\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-simple-siftDown-3-800x284.png\" alt=\"Vereinfachter siftDown-Algoriothmus: Verschieben der 5\" class=\"wp-image-29964\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-simple-siftDown-3-800x284.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-simple-siftDown-3-224x80.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-simple-siftDown-3-336x119.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-simple-siftDown-3-504x179.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-simple-siftDown-3-672x239.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-simple-siftDown-3-400x142.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-simple-siftDown-3-600x213.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-simple-siftDown-3-944x335.png 944w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-simple-siftDown-3-1200x426.png 1200w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-priority-queue-min-heap-simple-siftDown-3.png 1600w\" sizes=\"(max-width: 800px) 100vw, 800px\" \/><\/figure><\/div>\n\n\n\n<p>Wir haben die Min-Heap-Bedingung wiederhergestellt.<\/p>\n\n\n\n<p>Die Sift-Up- und Sift-Down-Operationen m\u00f6gen komplex erscheinen, sie k\u00f6nnen allerdings beide mit maximal 10 Zeilen Java-Code implementiert werden. Wie, erf\u00e4hrst du im n\u00e4chsten Kapitel.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"quellcode-fuer-priority-queue-mit-min-heap\">Quellcode f\u00fcr Priority Queue mit Min-Heap<\/h2>\n\n\n\n<p>Der folgende Quellcode zeigt, wie man eine Priority Queue mit einem Min-Heap implementiert (Klasse <a rel=\"noopener\" href=\"https:\/\/github.com\/SvenWoltmann\/java-collections-guide\/blob\/main\/src\/main\/java\/eu\/happycoders\/collections\/queue\/HeapPriorityQueue.java\" target=\"_blank\">HeapPriorityQueue<\/a> im GitHub-Repository). Aufgrund der L\u00e4nge der Klasse zeige ich sie im Folgenden abschnittsweise.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"konstruktoren\">Konstruktoren<\/h3>\n\n\n\n<p>Es gibt zwei Konstrukturen: einen, bei dem man die initiale Gr\u00f6\u00dfe des Arrays angeben kann und einen Default-Konstruktor, der die initiale Kapazit\u00e4t auf zehn setzt:<\/p>\n\n\n<pre class=\"wp-block-code\" aria-describedby=\"shcb-language-4\" data-shcb-language-name=\"Java\" data-shcb-language-slug=\"java\"><span><code class=\"hljs language-java\"><span class=\"hljs-keyword\">public<\/span> <span class=\"hljs-class\"><span class=\"hljs-keyword\">class<\/span> <span class=\"hljs-title\">HeapPriorityQueue<\/span>&lt;<span class=\"hljs-title\">E<\/span> <span class=\"hljs-keyword\">extends<\/span> <span class=\"hljs-title\">Comparable<\/span>&lt;? <span class=\"hljs-title\">super<\/span> <span class=\"hljs-title\">E<\/span>&gt;&gt; <span class=\"hljs-keyword\">implements<\/span> <span class=\"hljs-title\">Queue<\/span>&lt;<span class=\"hljs-title\">E<\/span>&gt; <\/span>{\n\n  <span class=\"hljs-keyword\">private<\/span> <span class=\"hljs-keyword\">static<\/span> <span class=\"hljs-keyword\">final<\/span> <span class=\"hljs-keyword\">int<\/span> DEFAULT_INITIAL_CAPACITY = <span class=\"hljs-number\">10<\/span>;\n  <span class=\"hljs-keyword\">private<\/span> <span class=\"hljs-keyword\">static<\/span> <span class=\"hljs-keyword\">final<\/span> <span class=\"hljs-keyword\">int<\/span> ROOT_INDEX = <span class=\"hljs-number\">0<\/span>;\n\n  <span class=\"hljs-keyword\">private<\/span> Object&#091;] elements;\n  <span class=\"hljs-keyword\">private<\/span> <span class=\"hljs-keyword\">int<\/span> numberOfElements;\n\n  <span class=\"hljs-function\"><span class=\"hljs-keyword\">public<\/span> <span class=\"hljs-title\">HeapPriorityQueue<\/span><span class=\"hljs-params\">()<\/span> <\/span>{\n    <span class=\"hljs-keyword\">this<\/span>(DEFAULT_INITIAL_CAPACITY);\n  }\n\n  <span class=\"hljs-function\"><span class=\"hljs-keyword\">public<\/span> <span class=\"hljs-title\">HeapPriorityQueue<\/span><span class=\"hljs-params\">(<span class=\"hljs-keyword\">int<\/span> capacity)<\/span> <\/span>{\n    <span class=\"hljs-keyword\">if<\/span> (capacity &lt; <span class=\"hljs-number\">1<\/span>) {\n      <span class=\"hljs-keyword\">throw<\/span> <span class=\"hljs-keyword\">new<\/span> IllegalArgumentException(<span class=\"hljs-string\">\"Capacity must be 1 or higher\"<\/span>);\n    }\n\n    elements = <span class=\"hljs-keyword\">new<\/span> Object&#091;capacity];\n  }\n<\/code><\/span><small class=\"shcb-language\" id=\"shcb-language-4\"><span class=\"shcb-language__label\">Code-Sprache:<\/span> <span class=\"shcb-language__name\">Java<\/span> <span class=\"shcb-language__paren\">(<\/span><span class=\"shcb-language__slug\">java<\/span><span class=\"shcb-language__paren\">)<\/span><\/small><\/pre>\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"enqueue\">enqueue()<\/h3>\n\n\n\n<p>Die <code>enqueue()<\/code>-Methode pr\u00fcft zun\u00e4chst, ob das Array voll ist. Ist das der Fall, ruft sie die <code>grow()<\/code>-Methode auf, welche das Array in ein neues, gr\u00f6\u00dferes Array kopiert:<\/p>\n\n\n<pre class=\"wp-block-code\" aria-describedby=\"shcb-language-5\" data-shcb-language-name=\"Java\" data-shcb-language-slug=\"java\"><span><code class=\"hljs language-java\">  <span class=\"hljs-meta\">@Override<\/span>\n  <span class=\"hljs-function\"><span class=\"hljs-keyword\">public<\/span> <span class=\"hljs-keyword\">void<\/span> <span class=\"hljs-title\">enqueue<\/span><span class=\"hljs-params\">(E newElement)<\/span> <\/span>{\n    <span class=\"hljs-keyword\">if<\/span> (numberOfElements == elements.length) {\n      grow();\n    }\n    siftUp(newElement);\n    numberOfElements++;\n  }\n\n  <span class=\"hljs-function\"><span class=\"hljs-keyword\">private<\/span> <span class=\"hljs-keyword\">void<\/span> <span class=\"hljs-title\">grow<\/span><span class=\"hljs-params\">()<\/span> <\/span>{\n    <span class=\"hljs-keyword\">int<\/span> newCapacity = elements.length + elements.length \/ <span class=\"hljs-number\">2<\/span>;\n    elements = Arrays.copyOf(elements, newCapacity);\n  }<\/code><\/span><small class=\"shcb-language\" id=\"shcb-language-5\"><span class=\"shcb-language__label\">Code-Sprache:<\/span> <span class=\"shcb-language__name\">Java<\/span> <span class=\"shcb-language__paren\">(<\/span><span class=\"shcb-language__slug\">java<\/span><span class=\"shcb-language__paren\">)<\/span><\/small><\/pre>\n\n\n<p>Die <code>grow()<\/code>-Methode habe ich hier stark vereinfacht dargestellt, da der Fokus auf den <code>siftUp()<\/code>- und <code>siftDown()<\/code>-Methoden liegen soll.<\/p>\n\n\n\n<p>In der <a rel=\"noopener\" href=\"https:\/\/github.com\/SvenWoltmann\/java-collections-guide\/blob\/main\/src\/main\/java\/eu\/happycoders\/collections\/queue\/HeapPriorityQueue.java#L50\" target=\"_blank\">HeapPriorityQueue-Klasse im GitHub-Repository<\/a> vergr\u00f6\u00dfert die <code>grow()<\/code>-Methode das Array bis zu einer bestimmten Gr\u00f6\u00dfe (64 Elemente) um Faktor 2 und erst danach um Faktor 1,5. Au\u00dferdem wird dort sichergestellt, dass eine bestimmte Maximalgr\u00f6\u00dfe nicht \u00fcberschritten wird.<\/p>\n\n\n\n<p>Wenn wir sichergestellt haben, dass das Array gro\u00df genug ist, rufen wir die <code>siftUp()<\/code>-Methode auf:<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"siftup\">siftUp()<\/h3>\n\n\n<pre class=\"wp-block-code\" aria-describedby=\"shcb-language-6\" data-shcb-language-name=\"Java\" data-shcb-language-slug=\"java\"><span><code class=\"hljs language-java\">  <span class=\"hljs-function\"><span class=\"hljs-keyword\">private<\/span> <span class=\"hljs-keyword\">void<\/span> <span class=\"hljs-title\">siftUp<\/span><span class=\"hljs-params\">(E newElement)<\/span> <\/span>{\n    <span class=\"hljs-keyword\">int<\/span> insertIndex = numberOfElements;\n\n    <span class=\"hljs-keyword\">while<\/span> (isNotRoot(insertIndex) &amp;&amp; isParentGreater(insertIndex, newElement)) {\n      copyParentDownTo(insertIndex);\n      insertIndex = parentOf(insertIndex);\n    }\n\n    elements&#091;insertIndex] = newElement;\n  }\n\n  <span class=\"hljs-function\"><span class=\"hljs-keyword\">private<\/span> <span class=\"hljs-keyword\">boolean<\/span> <span class=\"hljs-title\">isNotRoot<\/span><span class=\"hljs-params\">(<span class=\"hljs-keyword\">int<\/span> index)<\/span> <\/span>{\n    <span class=\"hljs-keyword\">return<\/span> index != ROOT_INDEX;\n  }\n\n  <span class=\"hljs-function\"><span class=\"hljs-keyword\">private<\/span> <span class=\"hljs-keyword\">boolean<\/span> <span class=\"hljs-title\">isParentGreater<\/span><span class=\"hljs-params\">(<span class=\"hljs-keyword\">int<\/span> insertIndex, E element)<\/span> <\/span>{\n    <span class=\"hljs-keyword\">int<\/span> parentIndex = parentOf(insertIndex);\n    E parent = elementAt(parentIndex);\n    <span class=\"hljs-keyword\">return<\/span> parent.compareTo(element) &gt; <span class=\"hljs-number\">0<\/span>;\n  }\n\n  <span class=\"hljs-function\"><span class=\"hljs-keyword\">private<\/span> <span class=\"hljs-keyword\">void<\/span> <span class=\"hljs-title\">copyParentDownTo<\/span><span class=\"hljs-params\">(<span class=\"hljs-keyword\">int<\/span> insertIndex)<\/span> <\/span>{\n    <span class=\"hljs-keyword\">int<\/span> parentIndex = parentOf(insertIndex);\n    elements&#091;insertIndex] = elements&#091;parentIndex];\n  }\n\n  <span class=\"hljs-function\"><span class=\"hljs-keyword\">private<\/span> <span class=\"hljs-keyword\">int<\/span> <span class=\"hljs-title\">parentOf<\/span><span class=\"hljs-params\">(<span class=\"hljs-keyword\">int<\/span> index)<\/span> <\/span>{\n    <span class=\"hljs-keyword\">return<\/span> (index - <span class=\"hljs-number\">1<\/span>) \/ <span class=\"hljs-number\">2<\/span>;\n  }\n<\/code><\/span><small class=\"shcb-language\" id=\"shcb-language-6\"><span class=\"shcb-language__label\">Code-Sprache:<\/span> <span class=\"shcb-language__name\">Java<\/span> <span class=\"shcb-language__paren\">(<\/span><span class=\"shcb-language__slug\">java<\/span><span class=\"shcb-language__paren\">)<\/span><\/small><\/pre>\n\n\n<p>Beachte, dass ich versucht habe den Algorithmus so verst\u00e4ndlich wie m\u00f6glich (und nicht so performant wie m\u00f6glich) zu implementieren. Die <code>parentOf()<\/code>-Methode wird in jeder Iteration drei Mal aufgerufen: einmal von <code>isParentGreater()<\/code>, einmal von <code>copyParentDownTo()<\/code> und einmal direkt.<\/p>\n\n\n\n<p>Eine verbesserten Variante (Klasse <a href=\"https:\/\/github.com\/SvenWoltmann\/java-collections-guide\/blob\/main\/src\/main\/java\/eu\/happycoders\/collections\/queue\/OptimizedHeapPriorityQueue.java#L74\">OptimizedHeapPriorityQueue<\/a> im GitHub-Repo, ab Zeile 74) zeigt einen optimierten Algorithmus, der den Elternindex nur ein Mal berechnet.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"dequeue\">dequeue()<\/h3>\n\n\n\n<p>Die <code>dequeue()<\/code>-Methode entnimmt das Kopf-Element, entfernt das letzte Element und ruft dann <code>siftDown()<\/code> auf, das letztendlich dieses letzte Element an seine neue Position verschiebt. <\/p>\n\n\n<pre class=\"wp-block-code\" aria-describedby=\"shcb-language-7\" data-shcb-language-name=\"Java\" data-shcb-language-slug=\"java\"><span><code class=\"hljs language-java\">  <span class=\"hljs-meta\">@Override<\/span>\n  <span class=\"hljs-function\"><span class=\"hljs-keyword\">public<\/span> E <span class=\"hljs-title\">dequeue<\/span><span class=\"hljs-params\">()<\/span> <\/span>{\n    E result = elementAtHead();\n    E lastElement = removeLastElement();\n    siftDown(lastElement);\n    <span class=\"hljs-keyword\">return<\/span> result;\n  }\n\n  <span class=\"hljs-function\"><span class=\"hljs-keyword\">private<\/span> E <span class=\"hljs-title\">removeLastElement<\/span><span class=\"hljs-params\">()<\/span> <\/span>{\n    numberOfElements--;\n    E lastElement = elementAt(numberOfElements);\n    elements&#091;numberOfElements] = <span class=\"hljs-keyword\">null<\/span>;\n    <span class=\"hljs-keyword\">return<\/span> lastElement;\n  }\n<\/code><\/span><small class=\"shcb-language\" id=\"shcb-language-7\"><span class=\"shcb-language__label\">Code-Sprache:<\/span> <span class=\"shcb-language__name\">Java<\/span> <span class=\"shcb-language__paren\">(<\/span><span class=\"shcb-language__slug\">java<\/span><span class=\"shcb-language__paren\">)<\/span><\/small><\/pre>\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"siftdown\">siftDown()<\/h3>\n\n\n\n<p><code>siftDown()<\/code> ist die komplizierteste Methode, da sie einen Knoten immer mit ggf. zwei Kindknoten vergleichen muss.<\/p>\n\n\n<pre class=\"wp-block-code\" aria-describedby=\"shcb-language-8\" data-shcb-language-name=\"Java\" data-shcb-language-slug=\"java\"><span><code class=\"hljs language-java\">  <span class=\"hljs-function\"><span class=\"hljs-keyword\">private<\/span> <span class=\"hljs-keyword\">void<\/span> <span class=\"hljs-title\">siftDown<\/span><span class=\"hljs-params\">(E lastElement)<\/span> <\/span>{\n    <span class=\"hljs-keyword\">int<\/span> lastElementInsertIndex = ROOT_INDEX;\n    <span class=\"hljs-keyword\">while<\/span> (isGreaterThanAnyChild(lastElement, lastElementInsertIndex)) {\n      moveSmallestChildUpTo(lastElementInsertIndex);\n      lastElementInsertIndex = smallestChildOf(lastElementInsertIndex);\n    }\n\n    elements&#091;lastElementInsertIndex] = lastElement;\n  }\n\n  <span class=\"hljs-function\"><span class=\"hljs-keyword\">private<\/span> <span class=\"hljs-keyword\">boolean<\/span> <span class=\"hljs-title\">isGreaterThanAnyChild<\/span><span class=\"hljs-params\">(E element, <span class=\"hljs-keyword\">int<\/span> parentIndex)<\/span> <\/span>{\n    E leftChild = leftChildOf(parentIndex);\n    E rightChild = rightChildOf(parentIndex);\n\n    <span class=\"hljs-keyword\">return<\/span> leftChild != <span class=\"hljs-keyword\">null<\/span> &amp;&amp; element.compareTo(leftChild) &gt; <span class=\"hljs-number\">0<\/span>\n        || rightChild != <span class=\"hljs-keyword\">null<\/span> &amp;&amp; element.compareTo(rightChild) &gt; <span class=\"hljs-number\">0<\/span>;\n  }\n\n  <span class=\"hljs-function\"><span class=\"hljs-keyword\">private<\/span> E <span class=\"hljs-title\">leftChildOf<\/span><span class=\"hljs-params\">(<span class=\"hljs-keyword\">int<\/span> parentIndex)<\/span> <\/span>{\n    <span class=\"hljs-keyword\">int<\/span> leftChildIndex = leftChildIndexOf(parentIndex);\n    <span class=\"hljs-keyword\">return<\/span> exists(leftChildIndex) ? elementAt(leftChildIndex) : <span class=\"hljs-keyword\">null<\/span>;\n  }\n\n  <span class=\"hljs-function\"><span class=\"hljs-keyword\">private<\/span> <span class=\"hljs-keyword\">int<\/span> <span class=\"hljs-title\">leftChildIndexOf<\/span><span class=\"hljs-params\">(<span class=\"hljs-keyword\">int<\/span> parentIndex)<\/span> <\/span>{\n    <span class=\"hljs-keyword\">return<\/span> <span class=\"hljs-number\">2<\/span> * parentIndex + <span class=\"hljs-number\">1<\/span>;\n  }\n\n  <span class=\"hljs-function\"><span class=\"hljs-keyword\">private<\/span> E <span class=\"hljs-title\">rightChildOf<\/span><span class=\"hljs-params\">(<span class=\"hljs-keyword\">int<\/span> parentIndex)<\/span> <\/span>{\n    <span class=\"hljs-keyword\">int<\/span> rightChildIndex = rightChildIndexOf(parentIndex);\n    <span class=\"hljs-keyword\">return<\/span> exists(rightChildIndex) ? elementAt(rightChildIndex) : <span class=\"hljs-keyword\">null<\/span>;\n  }\n\n  <span class=\"hljs-function\"><span class=\"hljs-keyword\">private<\/span> <span class=\"hljs-keyword\">int<\/span> <span class=\"hljs-title\">rightChildIndexOf<\/span><span class=\"hljs-params\">(<span class=\"hljs-keyword\">int<\/span> parentIndex)<\/span> <\/span>{\n    <span class=\"hljs-keyword\">return<\/span> <span class=\"hljs-number\">2<\/span> * parentIndex + <span class=\"hljs-number\">2<\/span>;\n  }\n\n  <span class=\"hljs-function\"><span class=\"hljs-keyword\">private<\/span> <span class=\"hljs-keyword\">boolean<\/span> <span class=\"hljs-title\">exists<\/span><span class=\"hljs-params\">(<span class=\"hljs-keyword\">int<\/span> index)<\/span> <\/span>{\n    <span class=\"hljs-keyword\">return<\/span> index &lt; numberOfElements;\n  }\n\n  <span class=\"hljs-function\"><span class=\"hljs-keyword\">private<\/span> <span class=\"hljs-keyword\">void<\/span> <span class=\"hljs-title\">moveSmallestChildUpTo<\/span><span class=\"hljs-params\">(<span class=\"hljs-keyword\">int<\/span> parentIndex)<\/span> <\/span>{\n    <span class=\"hljs-keyword\">int<\/span> smallestChildIndex = smallestChildOf(parentIndex);\n    elements&#091;parentIndex] = elements&#091;smallestChildIndex];\n  }\n\n  <span class=\"hljs-function\"><span class=\"hljs-keyword\">private<\/span> <span class=\"hljs-keyword\">int<\/span> <span class=\"hljs-title\">smallestChildOf<\/span><span class=\"hljs-params\">(<span class=\"hljs-keyword\">int<\/span> parentIndex)<\/span> <\/span>{\n    <span class=\"hljs-keyword\">int<\/span> leftChildIndex = leftChildIndexOf(parentIndex);\n    <span class=\"hljs-keyword\">int<\/span> rightChildIndex = rightChildIndexOf(parentIndex);\n\n    <span class=\"hljs-keyword\">if<\/span> (!exists(rightChildIndex)) {\n      <span class=\"hljs-keyword\">return<\/span> leftChildIndex;\n    }\n\n    <span class=\"hljs-keyword\">return<\/span> smallerOf(leftChildIndex, rightChildIndex);\n  }\n\n  <span class=\"hljs-function\"><span class=\"hljs-keyword\">private<\/span> <span class=\"hljs-keyword\">int<\/span> <span class=\"hljs-title\">smallerOf<\/span><span class=\"hljs-params\">(<span class=\"hljs-keyword\">int<\/span> leftChildIndex, <span class=\"hljs-keyword\">int<\/span> rightChildIndex)<\/span> <\/span>{\n    E leftChild = elementAt(leftChildIndex);\n    E rightChild = elementAt(rightChildIndex);\n    <span class=\"hljs-keyword\">return<\/span> leftChild.compareTo(rightChild) &lt; <span class=\"hljs-number\">0<\/span> ? leftChildIndex : rightChildIndex;\n  }\n<\/code><\/span><small class=\"shcb-language\" id=\"shcb-language-8\"><span class=\"shcb-language__label\">Code-Sprache:<\/span> <span class=\"shcb-language__name\">Java<\/span> <span class=\"shcb-language__paren\">(<\/span><span class=\"shcb-language__slug\">java<\/span><span class=\"shcb-language__paren\">)<\/span><\/small><\/pre>\n\n\n<p>Genau wie <code>siftUp()<\/code> habe ich auch <code>siftDown()<\/code> mit Fokus auf Lesbarkeit geschrieben, nicht auf Performance. So werden hier pro Iteration drei Mal die Positionen der Kindelemente berechnet: in <code>isGreaterThanAnyChild()<\/code>, in <code>moveSmallestChildUpTo()<\/code> und noch einmal in <code>smallestChildOf()<\/code>.<\/p>\n\n\n\n<p>In der optimierten Klasse <a rel=\"noopener\" href=\"https:\/\/github.com\/SvenWoltmann\/java-collections-guide\/blob\/main\/src\/main\/java\/eu\/happycoders\/collections\/queue\/OptimizedHeapPriorityQueue.java\" target=\"_blank\">OptimizedHeapPriorityQueue<\/a> werden diese Positionen nur einmal berechnet. Dadurch ist der Code aber auch nicht mehr ganz so leicht zu lesen.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"peek-isempty-und-zwei-hilfsmethoden\">peek(), isEmpty() und zwei Hilfsmethoden<\/h3>\n\n\n\n<p>Und zum Schluss noch die <code>peek()<\/code>- und <code>isEmpty()<\/code>-Methoden sowie zwei Hilfsmethoden, die verwendet werden, um das Element vom Kopf der Queue oder von einer spezifischen Position zu lesen.<\/p>\n\n\n\n<p>Da wir die Elemente in einem <code>Object<\/code>-Array speichern, m\u00fcssen die Array-Elemente nach <code>E<\/code> gecastet werden. Damit die Casts nicht \u00fcber den gesamten Quellcode verteilt sind, habe ich das Casten in eine zentrale Stelle, die Methode <code>elementAt()<\/code>, ausgelagert und dort die \"unchecked\"-Warnung einmalig unterdr\u00fcckt.<\/p>\n\n\n<pre class=\"wp-block-code\" aria-describedby=\"shcb-language-9\" data-shcb-language-name=\"Java\" data-shcb-language-slug=\"java\"><span><code class=\"hljs language-java\">  <span class=\"hljs-meta\">@Override<\/span>\n  <span class=\"hljs-function\"><span class=\"hljs-keyword\">public<\/span> E <span class=\"hljs-title\">peek<\/span><span class=\"hljs-params\">()<\/span> <\/span>{\n    <span class=\"hljs-keyword\">return<\/span> elementAtHead();\n  }\n\n  <span class=\"hljs-function\"><span class=\"hljs-keyword\">private<\/span> E <span class=\"hljs-title\">elementAtHead<\/span><span class=\"hljs-params\">()<\/span> <\/span>{\n    E element = elementAt(<span class=\"hljs-number\">0<\/span>);\n    <span class=\"hljs-keyword\">if<\/span> (element == <span class=\"hljs-keyword\">null<\/span>) {\n      <span class=\"hljs-keyword\">throw<\/span> <span class=\"hljs-keyword\">new<\/span> NoSuchElementException();\n    }\n    <span class=\"hljs-keyword\">return<\/span> element;\n  }\n\n  <span class=\"hljs-function\"><span class=\"hljs-keyword\">private<\/span> E <span class=\"hljs-title\">elementAt<\/span><span class=\"hljs-params\">(<span class=\"hljs-keyword\">int<\/span> child)<\/span> <\/span>{\n    <span class=\"hljs-meta\">@SuppressWarnings<\/span>(<span class=\"hljs-string\">\"unchecked\"<\/span>)\n    E element = (E) elements&#091;child];\n    <span class=\"hljs-keyword\">return<\/span> element;\n  }\n\n  <span class=\"hljs-meta\">@Override<\/span>\n  <span class=\"hljs-function\"><span class=\"hljs-keyword\">public<\/span> <span class=\"hljs-keyword\">boolean<\/span> <span class=\"hljs-title\">isEmpty<\/span><span class=\"hljs-params\">()<\/span> <\/span>{\n    <span class=\"hljs-keyword\">return<\/span> numberOfElements == <span class=\"hljs-number\">0<\/span>;\n  }\n}<\/code><\/span><small class=\"shcb-language\" id=\"shcb-language-9\"><span class=\"shcb-language__label\">Code-Sprache:<\/span> <span class=\"shcb-language__name\">Java<\/span> <span class=\"shcb-language__paren\">(<\/span><span class=\"shcb-language__slug\">java<\/span><span class=\"shcb-language__paren\">)<\/span><\/small><\/pre>\n\n\n<p>Wenn dir der Kopf noch nicht raucht, schau dir auch gerne einmal den <a href=\"https:\/\/github.com\/openjdk\/jdk\/blob\/master\/src\/java.base\/share\/classes\/java\/util\/PriorityQueue.java\" target=\"_blank\" rel=\"noopener\">Quellcode der PriorityQueue-Klasse des JDK<\/a> an. Diese kann Elemente nicht nur nach ihrer nat\u00fcrlichen Ordnung sortieren, sondern auch anhand eines dem Konstruktor \u00fcbergebenen Comparators.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"fazit\">Fazit<\/h2>\n\n\n\n<p>Damit endet diese Tutorial-Serie \u00fcber Queues. In dieser Serie hast du gelernt, wie eine Queue funktioniert, was bounded und unbounded, blocking und non-blocking Queues sind, welche Queue-Implementierungen es im JDK gibt und wie man Queues auf verschiedene Arten selbst implementieren kann.<\/p>\n\n\n\n<p>Wenn dir die Serie gefallen hat, hinterlasse mir gerne einen Kommantar oder teile die Artikel \u00fcber die Share-Buttons am Ende. Wenn du noch Fragen hast, kannst du sie gerne \u00fcber die Kommentar-Funktion stellen.<\/p>\n\n\n\n<p>M\u00f6chtest du \u00fcber neue Tutorials und Artikel informiert werden? Dann <a href=\"#\" data-formkit-toggle=\"d8ee997126\">klicke hier<\/a>, um dich f\u00fcr den HappyCoders.eu-Newsletter anzumelden.<a href=\"https:\/\/www.happycoders.eu\/de\/algorithmen\/stack-implementieren-queue\/\"><\/a><\/p>\n","protected":false},"excerpt":{"rendered":"<p>Wie implementiert man in Java eine Priority Queue mit einem Heap? Anschauliche Erkl\u00e4rung mit Diagrammen und Java-Quellcode.<\/p>\n","protected":false},"author":1,"featured_media":29993,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_seopress_robots_primary_cat":"none","_seopress_titles_title":"","_seopress_titles_desc":"Wie implementiert man in Java eine Priority Queue mit einem Heap? Anschauliche Erkl\u00e4rung mit Diagrammen und Java-Quellcode.","_seopress_robots_index":"","_uag_custom_page_level_css":"","_wp_convertkit_post_meta":{"form":"-1","landing_page":"","tag":"0","restrict_content":"0"},"_metis_text_type":"standard","_metis_text_length":17374,"_post_count":0,"footnotes":""},"categories":[127],"tags":[192],"class_list":["post-29914","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-algorithmen","tag-datenstrukturen-queue"],"uagb_featured_image_src":{"full":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/cairn-2753232-1770x986-1.jpg",1770,986,false],"thumbnail":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/cairn-2753232-1770x986-1.jpg",150,84,false],"medium":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/cairn-2753232-1770x986-1.jpg",300,167,false],"medium_large":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/cairn-2753232-1770x986-1.jpg",768,428,false],"large":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/cairn-2753232-1770x986-1.jpg",1024,570,false],"feature_thumb_224":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/cairn-2753232-1770x986-1-224x125.jpg",224,125,true],"feature_thumb_336":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/cairn-2753232-1770x986-1-336x187.jpg",336,187,true],"feature_thumb_504":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/cairn-2753232-1770x986-1-504x281.jpg",504,281,true],"feature_thumb_672":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/cairn-2753232-1770x986-1-672x374.jpg",672,374,true],"half_400":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/cairn-2753232-1770x986-1-400x223.jpg",400,223,true],"half_600":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/cairn-2753232-1770x986-1-600x334.jpg",600,334,true],"full_800":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/cairn-2753232-1770x986-1-800x446.jpg",800,446,true],"full_944":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/cairn-2753232-1770x986-1-944x526.jpg",944,526,true],"full_1200":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/cairn-2753232-1770x986-1-1200x668.jpg",1200,668,true],"wide_1180":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/cairn-2753232-1770x986-1-1180x490.jpg",1180,490,true],"wide_1770":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/cairn-2753232-1770x986-1-1770x735.jpg",1770,735,true],"1536x1536":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/cairn-2753232-1770x986-1.jpg",1536,856,false],"2048x2048":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/cairn-2753232-1770x986-1.jpg",1770,986,false]},"uagb_author_info":{"display_name":"Sven Woltmann","author_link":"https:\/\/www.happycoders.eu\/de\/author\/sven\/"},"uagb_comment_info":0,"uagb_excerpt":"Wie implementiert man in Java eine Priority Queue mit einem Heap? Anschauliche Erkl\u00e4rung mit Diagrammen und Java-Quellcode.","public_identification_id":"2c14a08fda514071bd4bb8e35f1664da","private_identification_id":"d2b11d26180c4c9c94b333345f2c87c7","_links":{"self":[{"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/posts\/29914","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/comments?post=29914"}],"version-history":[{"count":10,"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/posts\/29914\/revisions"}],"predecessor-version":[{"id":30184,"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/posts\/29914\/revisions\/30184"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/media\/29993"}],"wp:attachment":[{"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/media?parent=29914"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/categories?post=29914"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/tags?post=29914"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}