{"id":4825,"date":"2024-07-22T11:00:13","date_gmt":"2024-07-22T11:00:13","guid":{"rendered":"https:\/\/msgprogramator.sk\/?p=4825"},"modified":"2026-02-17T11:38:43","modified_gmt":"2026-02-17T11:38:43","slug":"heap-sort","status":"publish","type":"post","link":"https:\/\/msgprogramator.sk\/de\/heap-sort\/","title":{"rendered":"Heap sort &#8211; Heap-Sortierung in Java"},"content":{"rendered":"<p>Sortieralgorithmen werden verwendet, um die Elemente eines Arrays oder einer Liste in aufsteigender oder absteigender numerischer oder lexikografischer Reihenfolge neu zu ordnen. Die Sortierung ist sehr wichtig f\u00fcr die optimale Leistung anderer Algorithmen, die sortierte Eingabedaten ben\u00f6tigen. Es gibt eine Reihe von verschiedenen Sortieralgorithmen. Die Auswahl eines geeigneten Algorithmus h\u00e4ngt von Faktoren wie der Gr\u00f6\u00dfe und den Eigenschaften der Eingabedaten, dem verf\u00fcgbaren Speicher und den Zeit- und Platzanforderungen ab. Um dir die Auswahl zu erleichtern, werden wir in unserer Serie die bekanntesten Datensortieralgorithmen nacheinander vorstellen, ihre Prinzipien, Vor- und Nachteile erkl\u00e4ren und sie in Java programmieren. Bislang haben wir die folgenden Sortieralgorithmen behandelt:<\/p>\n<ul>\n<li><a href=\"https:\/\/msgprogramator.sk\/de\/sortieralgorithmen\/\" target=\"_blank\" rel=\"noopener\">Sortieralgorithmen<\/a> &#8211; Einf\u00fchrung in das Sortieren von Daten,<\/li>\n<li><a href=\"https:\/\/msgprogramator.sk\/de\/bubble-sort\/\" target=\"_blank\" rel=\"noopener\">Bubble sort<\/a> &#8211; Blasen-Sortierung,<\/li>\n<li><a href=\"https:\/\/msgprogramator.sk\/de\/comb-sort\/\" target=\"_blank\" rel=\"noopener\">Comb sort<\/a> &#8211; Kamm-Sortierung,<\/li>\n<li><a href=\"https:\/\/msgprogramator.sk\/de\/big-o-notation\/\" target=\"_blank\" rel=\"noopener\">Big O Notation &#8211;<\/a>Komplexit\u00e4tsanalyse von Algorithmen,<\/li>\n<li><a href=\"https:\/\/msgprogramator.sk\/de\/selection-sort\/\" target=\"_blank\" rel=\"noopener\">Auswahlsortierung<\/a> &#8211; Sortieren nach Auswahl,<\/li>\n<li><a href=\"https:\/\/msgprogramator.sk\/de\/insertion-sort\/\" target=\"_blank\" rel=\"noopener\">Einf\u00fcgungssortierung<\/a> &#8211; Sortieren nach Einf\u00fcgung,<\/li>\n<li><a href=\"https:\/\/msgprogramator.sk\/de\/counting-sort\/\" target=\"_blank\" rel=\"noopener\">Z\u00e4hlende Sortierung<\/a> &#8211; Sortieren durch Z\u00e4hlen.<\/li>\n<\/ul>\n<p>Heute werden wir uns das Sortieren mit Hilfe der <strong>Heap-Sort-Datenstruktur<\/strong> ansehen.<\/p>\n<h2>Haufen-Sortieren<\/h2>\n<p>Heapsort, der 1964 von J. W. J. Williams entwickelt wurde, ist ein recht popul\u00e4rer und sehr effizienter Sortieralgorithmus, der die Eingabedaten in einer Datenstruktur namens <strong>Heap <\/strong> speichert. Ein Heap ist ein vollst\u00e4ndiger Bin\u00e4rbaum (<strong>complete binary tree<\/strong>). Er besitzt eine interessante Eigenschaft, die es erm\u00f6glicht, die Eltern- und Kindknoten jedes beliebigen Knotens im Baum leicht zu finden. Dies liegt daran, wie der Heap aus einem Eingabearray konstruiert wird. Wenn der Index eines beliebigen Elements im Array i ist, dann gilt: Der linke Kindknoten hat den Index 2 * i + 1 Der rechte Kindknoten hat den Index 2 * i + 2 Der Elternknoten eines Elements mit Index i wird durch den ganzzahligen Wert von (i &#8211; 1) \/ 2 bestimmt. Der Wurzelknoten des Baums hat den Index 0. Gerade durch diese Indexarithmetik l\u00e4sst sich das Eingabearray in einen vollst\u00e4ndigen Bin\u00e4rbaum (Heap) abbilden, ohne dass zus\u00e4tzlicher Speicherplatz reserviert werden muss. Besondere Formen des Heaps sind der sogenannte Max-Heap und Min-Heap, die beide im Heapsort-Algorithmus verwendet werden. In einem Max-Heap gilt, dass der Wert jedes Elternknotens gr\u00f6\u00dfer ist als der seiner direkten (eine Ebene tiefer) und indirekten (zwei oder mehr Ebenen tiefer) Nachkommen. In einem Min-Heap ist der Wert des Elternknotens kleiner als der seiner Nachkommen. F\u00fcr die aufsteigende Sortierung der Elemente verwenden wir einen Max-Heap, wobei der maximale Wert des Baums im Wurzelknoten steht. F\u00fcr die absteigende Sortierung nutzen wir einen Min-Heap, bei dem der kleinste Wert im Wurzelknoten liegt.<\/p>\n<h2>Heap-Sort Algorithmus &#8211; Funktionsprinzip<\/h2>\n<p>Im ersten Schritt erstellen wir einen Heap aus dem eingegebenen Feature-Vektor. Wir wandeln diesen in die Max-Heap-Form um und erstellen daf\u00fcr eine heapify-Methode. Diese vergleicht rekursiv das \u00fcbergeordnete Element und seine Kinder und tauscht die Werte aus, um sicherzustellen, dass das Element mit dem h\u00f6chsten Wert an die Wurzel des Baums verschoben wird. Letzteres wird dann mit dem letzten Blatt des Baums ausgetauscht und dieses Blatt (mit dem h\u00f6chsten Wert) wird beschnitten. Dieses Element wird als sortiert betrachtet und die Gr\u00f6\u00dfe des Heaps wird um 1 reduziert. Durch den Austausch des Wurzelknotens hat der Heap seine Max-Heap-Form verloren und wir m\u00fcssen den gesamten Vorgang wiederholen. W\u00e4hrend wir nach und nach die aktuell h\u00f6chsten Werte aus dem Baum entfernen, f\u00fchren wir die Sortierung durch. Die Sortierung endet, wenn nur noch ein Element im Heap \u00fcbrig ist, das das kleinste ist und an die Spitze des Arrays geh\u00f6rt.<\/p>\n<h2>Vorteile des Heap-Sortieralgorithmus<\/h2>\n<ul>\n<li>Stabile Zeitkomplexit\u00e4t O(n log n) in allen F\u00e4llen,<\/li>\n<li>ben\u00f6tigt keinen zus\u00e4tzlichen Speicher,<\/li>\n<li>die Leistung des Algorithmus nicht mit der Menge der Eingabedaten abnimmt.<\/li>\n<\/ul>\n<h2>Nachteile des Heap-Sort Algorithmus<\/h2>\n<ul>\n<li>Ungeeignet f\u00fcr eine kleine Anzahl von Elementen, da sich der Overhead beim Erstellen und Verschieben von Elementen im Heap bemerkbar macht,<\/li>\n<li>ist nicht stabil,<\/li>\n<li>ist nicht anpassungsf\u00e4hig.<\/li>\n<\/ul>\n<h2>Zeitbedarf f\u00fcr Heap-Sortierung<\/h2>\n<table width=\"536\">\n<thead>\n<tr>\n<th rowspan=\"2\" width=\"94\"><strong>Algorithmus<\/strong><\/th>\n<th rowspan=\"2\" width=\"84\"><strong>Methode<\/strong><\/th>\n<th colspan=\"3\" width=\"208\"><strong>Zeitliche Komplexit\u00e4t<\/strong><\/th>\n<th rowspan=\"2\" width=\"82\"><strong>Speicher<\/strong><\/th>\n<th rowspan=\"2\" width=\"69\"><strong>Stabil<\/strong><\/th>\n<\/tr>\n<tr>\n<th width=\"73\"><strong>schlechteste<\/strong><\/th>\n<th width=\"63\"><strong>durchschnittlich<\/strong><\/th>\n<th width=\"71\"><strong>beste<\/strong><\/th>\n<\/tr>\n<\/thead>\n<tbody>\n<tr>\n<td width=\"94\">Heap sort<\/td>\n<td width=\"84\">Auswahl<\/td>\n<td width=\"73\">O(n log n)<\/td>\n<td width=\"63\">O(n log n)<\/td>\n<td width=\"71\">O(n log n)<\/td>\n<td width=\"82\">O(1)<\/td>\n<td width=\"69\">Nein<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<h2>Heap sort Animation, Visualisierung, gif<\/h2>\n<p>Die Visualisierung der Heap-Sortierung sieht folgenderma\u00dfen aus:<\/p>\n<figure id=\"attachment_3977\" aria-describedby=\"caption-attachment-3977\" style=\"width: 476px\" class=\"wp-caption alignnone\"><img loading=\"lazy\" decoding=\"async\" class=\"wp-image-3975 size-full\" src=\"https:\/\/msgprogramator.sk\/wp-content\/uploads\/2024\/07\/Heap_sort_example.gif\" alt=\"Visualisierung von heap sort\" width=\"476\" height=\"438\" \/><figcaption id=\"caption-attachment-3977\" class=\"wp-caption-text\">Nagae, CC BY-SA 4.0, via Wikimedia Commons<\/figcaption><\/figure>\n<figure id=\"attachment_3980\" aria-describedby=\"caption-attachment-3980\" style=\"width: 280px\" class=\"wp-caption alignnone\"><img loading=\"lazy\" decoding=\"async\" class=\"wp-image-3978 size-full\" src=\"https:\/\/msgprogramator.sk\/wp-content\/uploads\/2024\/07\/Sorting_heapsort_anim.gif\" alt=\"Visualisierung von heap sort\" width=\"280\" height=\"214\" \/><figcaption id=\"caption-attachment-3980\" class=\"wp-caption-text\">RolandH, CC BY-SA 4.0, via Wikimedia Commons<\/figcaption><\/figure>\n<p><span style=\"font-size: 9pt\">Quelle: commons.wikimedia.org\/wiki\/Category:Animations_of_sort_algorithms<\/span><\/p>\n<p>Eine Animation des Algorithmus findest du z.B. auf <a href=\"https:\/\/www.toptal.com\/developers\/sorting-algorithms\" target=\"_blank\" rel=\"nofollow noopener\">Toptal.<\/a> Es gibt 8 Arten von Algorithmen, du kannst die Animation auch r\u00fcckw\u00e4rts abspielen. Auf dieser <a href=\"https:\/\/www.hackerearth.com\/practice\/algorithms\/sorting\/heap-sort\/tutorial\/\" target=\"_blank\" rel=\"nofollow noopener\">Seite<\/a> kannst du die Schritte des Algorithmus durchlaufen, so dass du den Zeitverbrauch des Algorithmus \u00fcberpr\u00fcfen kannst.<\/p>\n<h2>Heap-Sort-Implementierung, Java-Code<\/h2>\n<p>Wir werden nun die Implementierung des Heap-Sortieralgorithmus in Java zeigen.<\/p>\n<p><strong><u>HeapSort.java<\/u><\/strong><\/p>\n<pre><code class=\"language-java\" data-line=\"\">package sorting;\n\npublic class HeapSort {\n    public void sort(int data[])\n    {\n        \/\/ Don&#039;t sort if there are no elements\n        if(data.length == 0)\n            return;\n\n        \/\/ Build Max-Heap by rearranging array\n        for (int i = data.length \/ 2 - 1; i &gt;= 0; i--) {\n            heapify(data, data.length, i);\n        }\n\n        \/\/ Extract max element from the heap one by one\n        for (int i = data.length - 1; i &gt; 0; i--) {\n            int temp = data[0];\n            data[0] = data[i];\n            data[i] = temp;\n            System.out.print(&quot;max-heap root node extraction: &quot; + data[i] + &quot; -&gt; &quot;);\n            printArray(data);\n            System.out.println(&quot;&quot;);\n            \/\/ Heapify root node\n            heapify(data, i, 0);\n        }\n    }\n\n    \/\/ Heapify the subtree by the index i, where n is size of the heap\n    void heapify(int data[], int n, int i) {\n        System.out.print(&quot;heapify (&quot; + n + &quot;, &quot; + i + &quot;) on &quot;);\n        printArray(data);\n        \/\/ Find max of (root, left child, right child)\n        int max = i;\n        int left = 2 * i + 1;\n        int right = 2 * i + 2;\n\n        if (left &lt; n &amp;&amp; data[left] &gt; data[max])\n            max = left;\n\n        if (right &lt; n &amp;&amp; data[right] &gt; data[max])\n            max = right;\n\n        \/\/ Swap and continue heapifying if root is not max\n        if (max != i) {\n            int swap = data[i];\n            data[i] = data[max];\n            data[max] = swap;\n            System.out.println(&quot; =&gt; exchange &quot; + data[max] + &quot; for &quot; + data[i]);\n            heapify(data, n, max);\n        }\n        else {\n            System.out.println(&quot; =&gt; no change&quot;);\n        }\n    }\n\n    \/\/ Function to print an array\n    public void printArray(int data[])\n    {\n        for (int i = 0; i &lt; data.length; i++)\n            System.out.print(data[i] + &quot; &quot;);\n        \/\/System.out.println();\n    }\n}<\/code><\/pre>\n<p>&nbsp;<\/p>\n<p><strong><u>Main.java<\/u><\/strong><\/p>\n<pre><code class=\"language-java\" data-line=\"\">import sorting.HeapSort;\n\npublic class Main {\n    public static void main(String[] args) {\n        int dataToSort[] = { 6, 5, 4, 2, 3, 1, 7 };\n        HeapSort heapSort = new HeapSort();\n        System.out.print(&quot;Input: &quot;);\n        heapSort.printArray(dataToSort);\n        System.out.println(&quot;&quot;);\n        heapSort.sort(dataToSort);\n        System.out.print(&quot;Sorted: &quot;);\n        heapSort.printArray(dataToSort);\n    }\n}<\/code><\/pre>\n<p>Die Ausgabe dieses Beispiels ist:<br \/>\n<img loading=\"lazy\" decoding=\"async\" class=\"wp-image-3966 size-full\" src=\"https:\/\/msgprogramator.sk\/wp-content\/uploads\/2024\/07\/heap-sort-vystup-z-prikladu-600-825.webp\" alt=\"Die Ausgabe dieses Beispiels\" width=\"600\" height=\"825\" srcset=\"https:\/\/msgprogramator.sk\/wp-content\/uploads\/2024\/07\/heap-sort-vystup-z-prikladu-600-825.webp 600w, https:\/\/msgprogramator.sk\/wp-content\/uploads\/2024\/07\/heap-sort-vystup-z-prikladu-600-825-218x300.webp 218w\" sizes=\"auto, (max-width: 600px) 100vw, 600px\" \/><\/p>\n<p>Wir haben die Dateien mit dem obigen Beispiel in Form von Code vorbereitet, den du direkt in Java ausf\u00fchren kannst. Lade <a href=\"https:\/\/msgprogramator.sk\/wp-content\/uploads\/2024\/07\/HeapSort.zip\" target=\"_blank\" rel=\"noopener\">Java Heap Sort Code<\/a> hier herunter.<\/p>\n<p>Wenn du ein <a href=\"https:\/\/msg-life.sk\/de\/stellenangebote\/java-entwickler-senior\/\" target=\"_blank\" rel=\"noopener\">Java Programmierer<\/a> bist und nach Arbeit suchst, schau dir unsere <a href=\"https:\/\/msg-life.sk\/de\/mitarbeiter-benefits\/\" target=\"_blank\" rel=\"noopener\">Mitareiterbenefits <\/a> an und reagiere auf die <a href=\"https:\/\/msg-life.sk\/de\/stellenangebote\/\" target=\"_blank\" rel=\"noopener\">neuesten Stellenangebote<\/a>.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>In diesem Artikel erf\u00e4hrst du, was Heap Sort ist, sein Prinzip, seine Vorteile, seine Nachteile, seine Visualisierung und seinen Java-Beispielcode.<\/p>\n","protected":false},"author":14,"featured_media":3971,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_acf_changed":false,"footnotes":""},"categories":[57],"tags":[],"class_list":["post-4825","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-java"],"acf":[],"aioseo_notices":[],"_links":{"self":[{"href":"https:\/\/msgprogramator.sk\/de\/wp-json\/wp\/v2\/posts\/4825","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/msgprogramator.sk\/de\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/msgprogramator.sk\/de\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/msgprogramator.sk\/de\/wp-json\/wp\/v2\/users\/14"}],"replies":[{"embeddable":true,"href":"https:\/\/msgprogramator.sk\/de\/wp-json\/wp\/v2\/comments?post=4825"}],"version-history":[{"count":5,"href":"https:\/\/msgprogramator.sk\/de\/wp-json\/wp\/v2\/posts\/4825\/revisions"}],"predecessor-version":[{"id":9722,"href":"https:\/\/msgprogramator.sk\/de\/wp-json\/wp\/v2\/posts\/4825\/revisions\/9722"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/msgprogramator.sk\/de\/wp-json\/wp\/v2\/media\/3971"}],"wp:attachment":[{"href":"https:\/\/msgprogramator.sk\/de\/wp-json\/wp\/v2\/media?parent=4825"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/msgprogramator.sk\/de\/wp-json\/wp\/v2\/categories?post=4825"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/msgprogramator.sk\/de\/wp-json\/wp\/v2\/tags?post=4825"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}