{"id":12216,"date":"2020-08-19T09:00:00","date_gmt":"2020-08-19T07:00:00","guid":{"rendered":"https:\/\/www.happycoders.eu\/?p=12216"},"modified":"2025-06-12T09:24:54","modified_gmt":"2025-06-12T07:24:54","slug":"heapsort","status":"publish","type":"post","link":"https:\/\/www.happycoders.eu\/de\/algorithmen\/heapsort\/","title":{"rendered":"Heapsort \u2013 Algorithmus, Quellcode, Zeitkomplexit\u00e4t"},"content":{"rendered":"\n<p>Bei Heapsort denkt jeder Java-Entwickler zun\u00e4chst an den Java-Heap. Dass Heapsort damit nichts zu tun hat \u2013 und wie Heapsort genau funktioniert \u2013 zeigt dir dieser Artikel.<\/p>\n\n\n\n<p>Im Detail erf\u00e4hrst du:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Was ist ein Heap?<\/li>\n\n\n\n<li>Wie funktioniert der Heapsort-Algorithmus?<\/li>\n\n\n\n<li>Wie sieht der Quellcode von Heapsort aus?<\/li>\n\n\n\n<li>Wie bestimmt man die Zeitkomplexit\u00e4t von Heapsort?<\/li>\n\n\n\n<li>Was ist Bottom-Up-Heapsort und welche Vorteile hat es?<\/li>\n\n\n\n<li>Wie schl\u00e4gt sich Heapsort im Vergleich zu Quicksort und Mergesort?<\/li>\n<\/ul>\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\" (deutsch: \"Haufen\" oder \"Halde\") bezeichnet einen <a href=\"\/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>Hier ist ein einfaches Beispiel f\u00fcr einen \"Max Heap\":<\/p>\n\n\n<div class=\"wp-block-image hc-image-margins\">\n<figure class=\"aligncenter size-full is-resized\"><img decoding=\"async\" width=\"656\" height=\"458\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_max_heap_example-v2.png\" alt=\"Beispiel f\u00fcr einen &quot;Max Heap&quot;\" class=\"wp-image-15466\" style=\"width:328px;height:229px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_max_heap_example-v2.png 656w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_max_heap_example-v2-224x156.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_max_heap_example-v2-336x235.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_max_heap_example-v2-504x352.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_max_heap_example-v2-400x279.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_max_heap_example-v2-600x419.png 600w\" sizes=\"(max-width: 656px) 100vw, 656px\" \/><\/figure>\n<\/div>\n\n\n<p>Die 9 ist gr\u00f6\u00dfer als die 8 und die 5; die 8 ist gr\u00f6\u00dfer als die 7 und die 2; usw.<\/p>\n\n\n\n<p>Ein Heap wird auf ein Array projiziert, indem dessen Elemente von oben links zeilenweise nach rechts unten in das Array \u00fcbertragen werden:<\/p>\n\n\n<div class=\"wp-block-image hc-image-margins\">\n<figure class=\"aligncenter size-full is-resized\"><img decoding=\"async\" width=\"682\" height=\"456\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_max_heap_to_array-v2.png\" alt=\"Projektion eines &quot;Max Heap&quot; auf ein Array\" class=\"wp-image-15465\" style=\"width:341px;height:228px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_max_heap_to_array-v2.png 682w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_max_heap_to_array-v2-224x150.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_max_heap_to_array-v2-336x225.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_max_heap_to_array-v2-504x337.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_max_heap_to_array-v2-672x449.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_max_heap_to_array-v2-400x267.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_max_heap_to_array-v2-600x401.png 600w\" sizes=\"(max-width: 682px) 100vw, 682px\" \/><\/figure>\n<\/div>\n\n\n<p>Der oben gezeigte Heap sieht als Array also so aus:<\/p>\n\n\n<div class=\"wp-block-image hc-image-margins\">\n<figure class=\"aligncenter size-full is-resized\"><img decoding=\"async\" width=\"802\" height=\"76\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_max_heap_as_array-v2.png\" alt=\"&quot;Max Heap&quot; als Array\" class=\"wp-image-15464\" style=\"width:401px;height:38px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_max_heap_as_array-v2.png 802w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_max_heap_as_array-v2-224x21.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_max_heap_as_array-v2-336x32.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_max_heap_as_array-v2-504x48.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_max_heap_as_array-v2-672x64.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_max_heap_as_array-v2-400x38.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_max_heap_as_array-v2-600x57.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_max_heap_as_array-v2-800x76.png 800w\" sizes=\"(max-width: 802px) 100vw, 802px\" \/><\/figure>\n<\/div>\n\n\n<p>Bei einem \"Max Heap\" ist das gr\u00f6\u00dfte Element immer ganz oben \u2013 in der Array-Form ist es folglich ganz links. Wie man diese Eigenschaft zum Sortieren verwenden kann, erf\u00e4hrst du im folgenden Abschnitt.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"heapsort-algorithmus\">Heapsort-Algorithmus<\/h2>\n\n\n\n<p>Der Heapsort-Algorithmus besteht aus zwei Phasen: In der ersten Phase wird das zu sortierende Array in einen Max Heap umgewandelt. Und in der zweiten Phase wird jeweils das gr\u00f6\u00dfte Element (also das an der Baumwurzel) entnommen und aus den restlichen Elementen erneut ein Max Heap hergestellt.<\/p>\n\n\n<div class=\"convertkit-form wp-block-convertkit-form\" style=\"\"><script async data-uid=\"5c918c0177\" src=\"https:\/\/happycoders.kit.com\/5c918c0177\/index.js\" data-jetpack-boost=\"ignore\" data-no-defer=\"1\" data-no-optimize=\"1\" nowprocket><\/script><\/div>\n\n\n\n<p>Die folgenden Abschnitte erkl\u00e4ren die zwei Phasen im Detail anhand eines Beispiels:<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"phase-1-heap-erstellen\">Phase 1: Heap erstellen<\/h3>\n\n\n\n<p>Das zu sortierende Array muss zun\u00e4chst in einen Heap umgewandelt werden. Dazu wird keine neue Datenstruktur angelegt, sondern die Zahlen werden innerhalb des Arrays so umsortiert, dass die oben beschriebene Heap-Struktur entsteht.<\/p>\n\n\n\n<p>Wie dies geschieht erkl\u00e4re ich in folgendem Beispiel anhand der aus den vorangegangenen Teilen der Artikelserie bekannten Zahlenfolge [3, 7, 1, 8, 2, 5, 9, 4, 6].<\/p>\n\n\n\n<p>Diese \"projizieren\" wir wie oben beschrieben auf einen Bin\u00e4rbaum. Dabei ist der Bin\u00e4rbaum keine separate Datenstruktur, sondern lediglich ein Gedankenkonstrukt \u2013 im Speicher liegen die Elemente ausschlie\u00dflich in dem Array.<\/p>\n\n\n<div class=\"wp-block-image hc-image-margins\">\n<figure class=\"aligncenter size-full is-resized\"><img decoding=\"async\" width=\"666\" height=\"518\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_buildheap_algorithm_step01.png\" alt=\"Heapsort - buildHeap - Schritt 1\" class=\"wp-image-15512\" style=\"width:333px;height:259px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_buildheap_algorithm_step01.png 666w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_buildheap_algorithm_step01-224x174.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_buildheap_algorithm_step01-336x261.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_buildheap_algorithm_step01-504x392.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_buildheap_algorithm_step01-400x311.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_buildheap_algorithm_step01-600x467.png 600w\" sizes=\"(max-width: 666px) 100vw, 666px\" \/><\/figure>\n<\/div>\n\n\n<p>Dieser Baum entspricht noch keinem Max Heap. Dessen Definiton lautet ja, dass Eltern immer gr\u00f6\u00dfer oder gleich ihrer Kinder sind.<\/p>\n\n\n\n<p>Um einen Max Heap herzustellen, besuchen wir nun alle Elternknoten \u2013 r\u00fcckw\u00e4rts vom letzten bis zum ersten \u2013 und sorgen daf\u00fcr, dass die Heap-Bedingung f\u00fcr den jeweiligen Knoten und die darunter erf\u00fcllt ist. Dies machen wir mit der sogenannten <code>heapify()<\/code>-Funktion.<\/p>\n\n\n\n<h4 class=\"wp-block-heading\">Aufruf Nr. 1 der heapify-Funktion <\/h4>\n\n\n\n<p>Die <code>heapify()<\/code>-Funktion wird zuerst f\u00fcr den letzten Elternknoten aufgerufen. Elternknoten sind 3, 7, 1 und 8. Der letzte Elternknoten ist die 8. Die <code>heapify()<\/code>-Funktion pr\u00fcft, ob die Kinder kleiner sind als der Elternknoten. 4 und 6 sind kleiner als 8. An diesem Elternknoten ist die Heap-Bedingung also erf\u00fcllt, und die <code>heapify()<\/code>-Funktion ist beendet.<\/p>\n\n\n<div class=\"wp-block-image hc-image-margins\">\n<figure class=\"aligncenter size-full is-resized\"><img decoding=\"async\" width=\"666\" height=\"518\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_buildheap_algorithm_step02.png\" alt=\"Heapsort - buildHeap - Schritt 2\" class=\"wp-image-15515\" style=\"width:333px;height:259px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_buildheap_algorithm_step02.png 666w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_buildheap_algorithm_step02-224x174.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_buildheap_algorithm_step02-336x261.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_buildheap_algorithm_step02-504x392.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_buildheap_algorithm_step02-400x311.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_buildheap_algorithm_step02-600x467.png 600w\" sizes=\"(max-width: 666px) 100vw, 666px\" \/><\/figure>\n<\/div>\n\n\n<h4 class=\"wp-block-heading\">Aufruf Nr. 2 der heapify-Funktion<\/h4>\n\n\n\n<p>Als zweites wird <code>heapify()<\/code> f\u00fcr den vorletzten Knoten aufgerufen: die 1. Die Kinder 5 und 9 sind beide gr\u00f6\u00dfer als die 1, die Heap-Bedingung ist also verletzt. Um die Heap-Bedingung wiederherzustellen, tauschen wir nun das gr\u00f6\u00dfere Kind mit dem Elternknoten, also die 9 mit der 1. Die <code>heapify()<\/code>-Funktion ist damit wieder beendet.<\/p>\n\n\n<div class=\"wp-block-image hc-image-margins\">\n<figure class=\"aligncenter size-full is-resized\"><img decoding=\"async\" width=\"1546\" height=\"568\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_buildheap_algorithm_step03.png\" alt=\"Heapsort - buildHeap - Schritt 3\" class=\"wp-image-15517\" style=\"width:773px;height:284px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_buildheap_algorithm_step03.png 1546w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_buildheap_algorithm_step03-224x82.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_buildheap_algorithm_step03-336x123.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_buildheap_algorithm_step03-504x185.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_buildheap_algorithm_step03-672x247.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_buildheap_algorithm_step03-400x147.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_buildheap_algorithm_step03-600x220.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_buildheap_algorithm_step03-800x294.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_buildheap_algorithm_step03-944x347.png 944w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_buildheap_algorithm_step03-1200x441.png 1200w\" sizes=\"(max-width: 1546px) 100vw, 1546px\" \/><\/figure>\n<\/div>\n\n\n<h4 class=\"wp-block-heading\">Aufruf Nr. 3 der heapify-Funktion<\/h4>\n\n\n\n<p>Nun wird <code>heapify()<\/code> auf der 7 aufgerufen. Kindknoten sind 8 und 2, nur die 8 ist gr\u00f6\u00dfer als der Elternknoten. Wir tauschen also die 7 mit der 8:<\/p>\n\n\n<div class=\"wp-block-image hc-image-margins\">\n<figure class=\"aligncenter size-full is-resized\"><img decoding=\"async\" width=\"1544\" height=\"570\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_buildheap_algorithm_step04.png\" alt=\"Heapsort - buildHeap - Schritt 4\" class=\"wp-image-15523\" style=\"width:772px;height:285px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_buildheap_algorithm_step04.png 1544w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_buildheap_algorithm_step04-224x83.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_buildheap_algorithm_step04-336x124.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_buildheap_algorithm_step04-504x186.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_buildheap_algorithm_step04-672x248.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_buildheap_algorithm_step04-400x148.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_buildheap_algorithm_step04-600x222.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_buildheap_algorithm_step04-800x295.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_buildheap_algorithm_step04-944x348.png 944w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_buildheap_algorithm_step04-1200x443.png 1200w\" sizes=\"(max-width: 1544px) 100vw, 1544px\" \/><\/figure>\n<\/div>\n\n\n<p>Da der Kindknoten, den wir eben getauscht haben, selbst zwei Kinder hat, muss die <code>heapify()<\/code>-Funktion nun pr\u00fcfen, ob die Heap-Bedingung f\u00fcr diesen Kindknoten noch erf\u00fcllt ist. In diesem Fall ist die 7 gr\u00f6\u00dfer als 4 und 6, die Heap-Bedingung ist also erf\u00fcllt; die <code>heapify()<\/code>-Funktion ist damit beendet.<\/p>\n\n\n<div class=\"wp-block-image hc-image-margins\">\n<figure class=\"aligncenter size-full is-resized\"><img decoding=\"async\" width=\"666\" height=\"518\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_buildheap_algorithm_step05.png\" alt=\"Heapsort - buildHeap - Schritt 5\" class=\"wp-image-15525\" style=\"width:333px;height:259px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_buildheap_algorithm_step05.png 666w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_buildheap_algorithm_step05-224x174.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_buildheap_algorithm_step05-336x261.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_buildheap_algorithm_step05-504x392.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_buildheap_algorithm_step05-400x311.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_buildheap_algorithm_step05-600x467.png 600w\" sizes=\"(max-width: 666px) 100vw, 666px\" \/><\/figure>\n<\/div>\n\n\n<h4 class=\"wp-block-heading\">Aufruf Nr. 4 der heapify-Funktion<\/h4>\n\n\n\n<p>Jetzt sind wir bereits am Wurzelknoten mit dem Element 3 angekommen. Beide Kindknoten, 8 und 9 sind gr\u00f6\u00dfer, wobei die 9 das gr\u00f6\u00dfte Kind ist und daher mit dem Elternknoten vertauscht wird:<\/p>\n\n\n<div class=\"wp-block-image hc-image-margins\">\n<figure class=\"aligncenter size-full is-resized\"><img decoding=\"async\" width=\"1544\" height=\"570\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_buildheap_algorithm_step06.png\" alt=\"Heapsort - buildHeap - Schritt 6\" class=\"wp-image-15526\" style=\"width:772px;height:285px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_buildheap_algorithm_step06.png 1544w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_buildheap_algorithm_step06-224x83.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_buildheap_algorithm_step06-336x124.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_buildheap_algorithm_step06-504x186.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_buildheap_algorithm_step06-672x248.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_buildheap_algorithm_step06-400x148.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_buildheap_algorithm_step06-600x222.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_buildheap_algorithm_step06-800x295.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_buildheap_algorithm_step06-944x348.png 944w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_buildheap_algorithm_step06-1200x443.png 1200w\" sizes=\"(max-width: 1544px) 100vw, 1544px\" \/><\/figure>\n<\/div>\n\n\n<p>Wiederum hat der getauschte Kindknoten selbst Kinder, so dass wir die Heap-Bedingung an diesem Kindknoten \u00fcberpr\u00fcfen m\u00fcssen. Die 5 ist gr\u00f6\u00dfer als die 3, d. h. die Heap-Bedingung ist nicht erf\u00fcllt und muss durch Tauschen der 5 und der 3 wiederhergestellt werden:<\/p>\n\n\n<div class=\"wp-block-image hc-image-margins\">\n<figure class=\"aligncenter size-full is-resized\"><img decoding=\"async\" width=\"1546\" height=\"570\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_buildheap_algorithm_step07.png\" alt=\"Heapsort - buildHeap - Schritt 7\" class=\"wp-image-15528\" style=\"width:773px;height:285px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_buildheap_algorithm_step07.png 1546w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_buildheap_algorithm_step07-224x83.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_buildheap_algorithm_step07-336x124.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_buildheap_algorithm_step07-504x186.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_buildheap_algorithm_step07-672x248.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_buildheap_algorithm_step07-400x147.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_buildheap_algorithm_step07-600x221.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_buildheap_algorithm_step07-800x295.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_buildheap_algorithm_step07-944x348.png 944w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_buildheap_algorithm_step07-1200x442.png 1200w\" sizes=\"(max-width: 1546px) 100vw, 1546px\" \/><\/figure>\n<\/div>\n\n\n<p>Damit ist auch der vierte und letzte Aufruf der <code>heapify()<\/code>-Funktion beendet. Ein Max Heap ist entstanden:<\/p>\n\n\n<div class=\"wp-block-image hc-image-margins\">\n<figure class=\"aligncenter size-full is-resized\"><img decoding=\"async\" width=\"670\" height=\"518\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_buildheap_algorithm_step08.png\" alt=\"Heapsort - buildHeap - Schritt 8\" class=\"wp-image-15530\" style=\"width:335px;height:259px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_buildheap_algorithm_step08.png 670w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_buildheap_algorithm_step08-224x173.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_buildheap_algorithm_step08-336x260.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_buildheap_algorithm_step08-504x390.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_buildheap_algorithm_step08-400x309.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_buildheap_algorithm_step08-600x464.png 600w\" sizes=\"(max-width: 670px) 100vw, 670px\" \/><\/figure>\n<\/div>\n\n\n<p>Damit gehen wir \u00fcber in Phase zwei des Heapsort-Algorithmus.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"phase-2-sortieren-des-arrays\">Phase 2: Sortieren des Arrays<\/h3>\n\n\n\n<p>In Phase 2 machen wir uns die Tatsache zunutze, dass das gr\u00f6\u00dfte Element des Max Heaps immer an dessen Wurzel (bzw. im Array ganz links) steht.<\/p>\n\n\n\n<h4 class=\"wp-block-heading\">Phase 2, Schritt 1: Root und letztes Element tauschen<\/h4>\n\n\n\n<p>Das Wurzelelement (die 9) tauschen wir nun mit dem letzten Element (der 6), so dass die 9 an ihrer finalen Position am Ende des Arrays steht (im Array blau markiert). Au\u00dferdem entfernen wir dieses Element gedanklich aus dem Baum (im Baum grau dargestellt):<\/p>\n\n\n<div class=\"wp-block-image hc-image-margins\">\n<figure class=\"aligncenter size-full is-resized\"><img decoding=\"async\" width=\"1548\" height=\"572\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_algorithm_phase2_step01.png\" alt=\"Heapsort - Phase 2 - Schritt 1\" class=\"wp-image-15535\" style=\"width:774px;height:286px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_algorithm_phase2_step01.png 1548w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_algorithm_phase2_step01-224x83.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_algorithm_phase2_step01-336x124.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_algorithm_phase2_step01-504x186.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_algorithm_phase2_step01-672x248.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_algorithm_phase2_step01-400x148.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_algorithm_phase2_step01-600x222.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_algorithm_phase2_step01-800x296.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_algorithm_phase2_step01-944x349.png 944w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_algorithm_phase2_step01-1200x443.png 1200w\" sizes=\"(max-width: 1548px) 100vw, 1548px\" \/><\/figure>\n<\/div>\n\n\n<p>Nachdem wir die 6 an die Wurzel des Baumes gesetzt haben, ist dieser kein Max Heap mehr. Im n\u00e4chsten Schritt \"reparieren\" wir den Heap.<\/p>\n\n\n\n<h4 class=\"wp-block-heading\">Phase 2, Schritt 2: Heap-Bedingung wiederherstellen<\/h4>\n\n\n\n<p>Um die Heap-Bedingung wiederherzustellen, rufen wir die aus Phase 1 bekannte <code>heapify()<\/code>-Funktion auf dem Wurzelknoten auf. Wir vergleichen also die 6 mit ihren Kindern, 8 und 5. Die 8 ist gr\u00f6\u00dfer, wir tauschen sie daher mit der 6:<\/p>\n\n\n<div class=\"wp-block-image hc-image-margins\">\n<figure class=\"aligncenter size-full is-resized\"><img decoding=\"async\" width=\"1548\" height=\"570\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_algorithm_phase2_step02.png\" alt=\"Heapsort - Phase 2 - Schritt 2\" class=\"wp-image-15540\" style=\"width:774px;height:285px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_algorithm_phase2_step02.png 1548w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_algorithm_phase2_step02-224x82.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_algorithm_phase2_step02-336x124.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_algorithm_phase2_step02-504x186.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_algorithm_phase2_step02-672x247.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_algorithm_phase2_step02-400x147.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_algorithm_phase2_step02-600x221.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_algorithm_phase2_step02-800x295.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_algorithm_phase2_step02-944x348.png 944w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_algorithm_phase2_step02-1200x442.png 1200w\" sizes=\"(max-width: 1548px) 100vw, 1548px\" \/><\/figure>\n<\/div>\n\n\n<p>Der getauschte Kindknoten hat wiederum zwei Kinder, die 7 und die 2. Die 7 ist gr\u00f6\u00dfer als die 6, daher tauschen wir auch diese zwei Elemente:<\/p>\n\n\n<div class=\"wp-block-image hc-image-margins\">\n<figure class=\"aligncenter size-full is-resized\"><img decoding=\"async\" width=\"1546\" height=\"570\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_algorithm_phase2_step03.png\" alt=\"Heapsort - Phase 2 - Schritt 3\" class=\"wp-image-15541\" style=\"width:773px;height:285px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_algorithm_phase2_step03.png 1546w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_algorithm_phase2_step03-224x83.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_algorithm_phase2_step03-336x124.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_algorithm_phase2_step03-504x186.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_algorithm_phase2_step03-672x248.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_algorithm_phase2_step03-400x147.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_algorithm_phase2_step03-600x221.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_algorithm_phase2_step03-800x295.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_algorithm_phase2_step03-944x348.png 944w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_algorithm_phase2_step03-1200x442.png 1200w\" sizes=\"(max-width: 1546px) 100vw, 1546px\" \/><\/figure>\n<\/div>\n\n\n<p>Der getauschte Kindknoten hat auch noch ein Kind, die 4. Die 6 ist gr\u00f6\u00dfer als die 4, die Heap-Bedingung ist an diesem Knoten also erf\u00fcllt, so dass die <code>heapify()<\/code>-Funktion beendet ist und wir wieder einen Max Heap haben:<\/p>\n\n\n<div class=\"wp-block-image hc-image-margins\">\n<figure class=\"aligncenter size-full is-resized\"><img decoding=\"async\" width=\"670\" height=\"518\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_algorithm_phase2_step04.png\" alt=\"Heapsort - Phase 2 - Schritt 4\" class=\"wp-image-15543\" style=\"width:335px;height:259px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_algorithm_phase2_step04.png 670w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_algorithm_phase2_step04-224x173.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_algorithm_phase2_step04-336x260.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_algorithm_phase2_step04-504x390.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_algorithm_phase2_step04-400x309.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_algorithm_phase2_step04-600x464.png 600w\" sizes=\"(max-width: 670px) 100vw, 670px\" \/><\/figure>\n<\/div>\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"wiederholung-der-schritte\">Wiederholung der Schritte<\/h3>\n\n\n\n<p>Damit steht nun wieder die gr\u00f6\u00dfte Zahl des verbleibenden Arrays, die 8, an erster Stelle. Diese wird wieder mit dem letzten Element des Baums vertauscht. Da wir den Baum um ein Element gek\u00fcrzt haben, liegt das letzte Element des Baumes auf dem vorletzten Feld des Arrays:<\/p>\n\n\n<div class=\"wp-block-image hc-image-margins\">\n<figure class=\"aligncenter size-full is-resized\"><img decoding=\"async\" width=\"1600\" height=\"572\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_algorithm_phase2_step05.png\" alt=\"Heapsort - Phase 2 - Schritt 5\" class=\"wp-image-15545\" style=\"width:800px;height:286px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_algorithm_phase2_step05.png 1600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_algorithm_phase2_step05-224x80.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_algorithm_phase2_step05-336x120.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_algorithm_phase2_step05-504x180.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_algorithm_phase2_step05-672x240.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_algorithm_phase2_step05-400x143.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_algorithm_phase2_step05-600x215.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_algorithm_phase2_step05-800x286.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_algorithm_phase2_step05-944x337.png 944w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_algorithm_phase2_step05-1200x429.png 1200w\" sizes=\"(max-width: 1600px) 100vw, 1600px\" \/><\/figure>\n<\/div>\n\n\n<p>Damit sind die letzten zwei Felder des Arrays sortiert.<\/p>\n\n\n\n<p>An der Wurzel ist nun wieder die Heap-Bedingung verletzt, und wir reparieren den Baum, indem wir <code>heapify()<\/code> auf dem Wurzelelement aufrufen (das folgende Bild zeigt alle heapify-Schritte auf einmal).<\/p>\n\n\n<div class=\"wp-block-image hc-image-margins\">\n<figure class=\"aligncenter size-full is-resized\"><img decoding=\"async\" width=\"1548\" height=\"464\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_algorithm_phase2_step06.png\" alt=\"Heapsort - Phase 2 - Schritt 6\" class=\"wp-image-15547\" style=\"width:774px;height:232px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_algorithm_phase2_step06.png 1548w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_algorithm_phase2_step06-224x67.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_algorithm_phase2_step06-336x101.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_algorithm_phase2_step06-504x151.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_algorithm_phase2_step06-672x201.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_algorithm_phase2_step06-400x120.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_algorithm_phase2_step06-600x180.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_algorithm_phase2_step06-800x240.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_algorithm_phase2_step06-944x283.png 944w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_algorithm_phase2_step06-1200x360.png 1200w\" sizes=\"(max-width: 1548px) 100vw, 1548px\" \/><\/figure>\n<\/div>\n\n\n<p>Wir wiederholen den Prozess solange, bis der Baum nur noch ein Element enth\u00e4lt:<\/p>\n\n\n<div class=\"wp-block-image hc-image-margins\">\n<figure class=\"aligncenter size-full is-resized\"><img decoding=\"async\" width=\"1546\" height=\"412\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_algorithm_phase2_step07.png\" alt=\"Heapsort - Phase 2 - Schritt 7\" class=\"wp-image-15549\" style=\"width:773px;height:206px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_algorithm_phase2_step07.png 1546w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_algorithm_phase2_step07-224x60.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_algorithm_phase2_step07-336x90.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_algorithm_phase2_step07-504x134.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_algorithm_phase2_step07-672x179.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_algorithm_phase2_step07-400x107.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_algorithm_phase2_step07-600x160.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_algorithm_phase2_step07-800x213.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_algorithm_phase2_step07-944x252.png 944w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_algorithm_phase2_step07-1200x320.png 1200w\" sizes=\"(max-width: 1546px) 100vw, 1546px\" \/><\/figure>\n<\/div>\n\n\n<p>Dieses ist das kleinste und verbleibt am Anfang des Arrays. Der Algorithmus ist beendet, das Array ist sortiert:<\/p>\n\n\n<div class=\"wp-block-image hc-image-margins\">\n<figure class=\"aligncenter size-full is-resized\"><img decoding=\"async\" width=\"670\" height=\"64\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_algorithm_phase2_step08.png\" alt=\"Heapsort - Phase 2 - Schritt 8\" class=\"wp-image-15551\" style=\"width:335px;height:32px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_algorithm_phase2_step08.png 670w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_algorithm_phase2_step08-224x21.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_algorithm_phase2_step08-336x32.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_algorithm_phase2_step08-504x48.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_algorithm_phase2_step08-400x38.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_algorithm_phase2_step08-600x57.png 600w\" sizes=\"(max-width: 670px) 100vw, 670px\" \/><\/figure>\n<\/div>\n\n\n<h2 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"heapsort-java-code-beispiel\">Heapsort Java Code Beispiel<\/h2>\n\n\n\n<p>Im folgenden findest du den Quellcode von Heapsort.<\/p>\n\n\n\n<p>Die <code>sort()<\/code>-Methode ruft zun\u00e4chst <code>buildHeap()<\/code> auf, um den Heap initial aufzubauen. <\/p>\n\n\n\n<p>In der darauf folgenden Schleife iteriert die Variable <code>swapToPos<\/code> r\u00fcckw\u00e4rts vom Ende des Arrays bis zum zweiten Feld. Im Schleifenk\u00f6rper wird das erste Element mit demjenigen an der Position <code>swapToPos<\/code> vertauscht und danach die <code>heapify()<\/code>-Methode auf dem Sub-Array bis zur (ausschlie\u00dflichen) Position <code>swapToPos<\/code> aufgerufen:<\/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\"><span class=\"hljs-keyword\">public<\/span> <span class=\"hljs-class\"><span class=\"hljs-keyword\">class<\/span> <span class=\"hljs-title\">HeapSort<\/span> <\/span>{\n\n  <span class=\"hljs-function\"><span class=\"hljs-keyword\">public<\/span> <span class=\"hljs-keyword\">void<\/span> <span class=\"hljs-title\">sort<\/span><span class=\"hljs-params\">(<span class=\"hljs-keyword\">int<\/span>&#091;] elements)<\/span> <\/span>{\n    buildHeap(elements);\n\n    <span class=\"hljs-keyword\">for<\/span> (<span class=\"hljs-keyword\">int<\/span> swapToPos = elements.length - <span class=\"hljs-number\">1<\/span>; swapToPos &gt; <span class=\"hljs-number\">0<\/span>; swapToPos--) {\n      <span class=\"hljs-comment\">\/\/ Move root to end<\/span>\n      ArrayUtils.swap(elements, <span class=\"hljs-number\">0<\/span>, swapToPos);\n\n      <span class=\"hljs-comment\">\/\/ Fix remaining heap<\/span>\n      heapify(elements, swapToPos, <span class=\"hljs-number\">0<\/span>);\n    }\n  }\n\n  &#091;...]\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>Die <code>buildHeap()<\/code>-Methode ruft f\u00fcr jeden Elternknoten \u2013 beginnend beim letzten \u2013 <code>heapify()<\/code> auf und \u00fcbergibt dieser Methode das Array, die L\u00e4nge des Sub-Arrays, das den Heap darstellt und die Position des Elternknotens, an dem <code>heapify()<\/code> starten soll:<\/p>\n\n\n<pre class=\"wp-block-code\" aria-describedby=\"shcb-language-3\" data-shcb-language-name=\"Java\" data-shcb-language-slug=\"java\"><span><code class=\"hljs language-java\"><span class=\"hljs-function\"><span class=\"hljs-keyword\">void<\/span> <span class=\"hljs-title\">buildHeap<\/span><span class=\"hljs-params\">(<span class=\"hljs-keyword\">int<\/span>&#091;] elements)<\/span> <\/span>{\n  <span class=\"hljs-comment\">\/\/ \"Find\" the last parent node<\/span>\n  <span class=\"hljs-keyword\">int<\/span> lastParentNode = elements.length \/ <span class=\"hljs-number\">2<\/span> - <span class=\"hljs-number\">1<\/span>;\n\n  <span class=\"hljs-comment\">\/\/ Now heapify it from here on backwards<\/span>\n  <span class=\"hljs-keyword\">for<\/span> (<span class=\"hljs-keyword\">int<\/span> i = lastParentNode; i &gt;= <span class=\"hljs-number\">0<\/span>; i--) {\n    heapify(elements, elements.length, i);\n  }\n}<\/code><\/span><small class=\"shcb-language\" id=\"shcb-language-3\"><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>heapify()<\/code>-Methode pr\u00fcft, ob ein Kindknoten gr\u00f6\u00dfer ist als der Elternknoten. Wenn das der Fall ist, wird das Elternelement mit dem gr\u00f6\u00dferen Kindelement vertauscht, und der Prozess wird auf dem Kindknoten wiederholt.<\/p>\n\n\n\n<p>(Hier k\u00f6nnte man auch mit Rekursion arbeiten, was sich allerdings negativ auf die Platzkomplexit\u00e4t auswirken w\u00fcrde.)<\/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-function\"><span class=\"hljs-keyword\">void<\/span> <span class=\"hljs-title\">heapify<\/span><span class=\"hljs-params\">(<span class=\"hljs-keyword\">int<\/span>&#091;] heap, <span class=\"hljs-keyword\">int<\/span> length, <span class=\"hljs-keyword\">int<\/span> parentPos)<\/span> <\/span>{\n  <span class=\"hljs-keyword\">while<\/span> (<span class=\"hljs-keyword\">true<\/span>) {\n    <span class=\"hljs-keyword\">int<\/span> leftChildPos = parentPos * <span class=\"hljs-number\">2<\/span> + <span class=\"hljs-number\">1<\/span>;\n    <span class=\"hljs-keyword\">int<\/span> rightChildPos = parentPos * <span class=\"hljs-number\">2<\/span> + <span class=\"hljs-number\">2<\/span>;\n\n    <span class=\"hljs-comment\">\/\/ Find the largest element<\/span>\n    <span class=\"hljs-keyword\">int<\/span> largestPos = parentPos;\n    <span class=\"hljs-keyword\">if<\/span> (leftChildPos &lt; length &amp;&amp; heap&#091;leftChildPos] &gt; heap&#091;largestPos]) {\n      largestPos = leftChildPos;\n    }\n    <span class=\"hljs-keyword\">if<\/span> (rightChildPos &lt; length &amp;&amp; heap&#091;rightChildPos] &gt; heap&#091;largestPos]) {\n      largestPos = rightChildPos;\n    }\n\n    <span class=\"hljs-comment\">\/\/ largestPos is now either parentPos, leftChildPos or rightChildPos.<\/span>\n    <span class=\"hljs-comment\">\/\/ If it's the parent, we're done<\/span>\n    <span class=\"hljs-keyword\">if<\/span> (largestPos == parentPos) {\n      <span class=\"hljs-keyword\">break<\/span>;\n    }\n\n    <span class=\"hljs-comment\">\/\/ If it's not the parent, then switch!<\/span>\n    ArrayUtils.swap(heap, parentPos, largestPos);\n\n    <span class=\"hljs-comment\">\/\/ ... and fix again starting at the child we moved the parent to<\/span>\n    parentPos = largestPos;\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<p>Du findest den Quellcode in der Klasse <a rel=\"noopener\" href=\"https:\/\/github.com\/SvenWoltmann\/sorting-algorithms-ultimate-guide\/blob\/main\/src\/main\/java\/eu\/happycoders\/sort\/method\/heapsort\/Heapsort.java\" target=\"_blank\">HeapSort im GitHub-Repository<\/a>. Diese unterscheidet sich leicht von der hier abgedruckten Klasse: Die Klasse im Repository implementiert das Interface <code>SortAlgorithm<\/code>, um innerhalb des Testframeworks austauschbar zu sein.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"heapsort-zeitkomplexitaet\">Heapsort Zeitkomplexit\u00e4t<\/h2>\n\n\n\n<p>Klicke auf den folgenden Link f\u00fcr eine Einf\u00fchrung in <a href=\"https:\/\/www.happycoders.eu\/de\/algorithmen\/o-notation-zeitkomplexitaet\/\">\"Zeitkomplexit\u00e4t\" und \"O-Notation\"<\/a> (mit Beispielen und Diagrammen).<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"zeitkomplexitaet-der-heapify-methode\">Zeitkomplexit\u00e4t der heapify()-Methode<\/h3>\n\n\n\n<p>Fangen wir mit der <code>heapify()<\/code>-Funktion an, da diese auch f\u00fcr den initialen Aufbau des Heaps ben\u00f6tigt wird.<\/p>\n\n\n\n<p>In der <code>heapify()<\/code>-Funktion hangeln wir uns einmal von oben nach unten durch den Baum. Die H\u00f6he eines Bin\u00e4rbaumes (die Wurzel wird nicht mitgez\u00e4hlt) der Gr\u00f6\u00dfe <em>n<\/em> ist maximal <em>log<sub>2<\/sub> n<\/em>, d. h. bei einer Verdopplung der Anzahl Elemente wird der Baum lediglich eine Ebene tiefer:<\/p>\n\n\n<div class=\"wp-block-image hc-image-margins\">\n<figure class=\"aligncenter size-full is-resized\"><img decoding=\"async\" width=\"1168\" height=\"364\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_heapify_complexity_tree-v2.png\" alt=\"Heapsort - Zeitkomplexit\u00e4t heapify()-Methode\" class=\"wp-image-15460\" style=\"width:584px;height:182px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_heapify_complexity_tree-v2.png 1168w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_heapify_complexity_tree-v2-224x70.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_heapify_complexity_tree-v2-336x105.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_heapify_complexity_tree-v2-504x157.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_heapify_complexity_tree-v2-672x209.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_heapify_complexity_tree-v2-400x125.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_heapify_complexity_tree-v2-600x187.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_heapify_complexity_tree-v2-800x249.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_heapify_complexity_tree-v2-944x294.png 944w\" sizes=\"(max-width: 1168px) 100vw, 1168px\" \/><\/figure>\n<\/div>\n\n\n<p>Die Komplexit\u00e4t f\u00fcr die <code>heapify()<\/code>-Funktion ist entsprechend <em>O(log n)<\/em>.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"zeitkomplexitaet-der-buildheap-methode\">Zeitkomplexit\u00e4t der buildHeap()-Methode<\/h3>\n\n\n\n<p>F\u00fcr den erstmaligen Aufbau des Heaps wird f\u00fcr jeden Elternknoten \u2013 r\u00fcckw\u00e4rts, beginnend beim letzten Knoten und endend an der Baumwurzel \u2013 die <code>heapify()<\/code>-Methode aufgerufen.<\/p>\n\n\n\n<p>Ein Heap der Gr\u00f6\u00dfe <em>n<\/em> hat <em>n\/2 (abgerundet)<\/em> Elternknoten:<\/p>\n\n\n<div class=\"wp-block-image hc-image-margins\">\n<figure class=\"aligncenter size-full is-resized\"><img decoding=\"async\" width=\"1420\" height=\"386\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_buildheap_complexity.png\" alt=\"Heapsort-Zeitkomplexit\u00e4t: Anzahl und Reihenfolge der heapify()-Aufrufe durch buildHeap()\" class=\"wp-image-15469\" style=\"width:710px;height:193px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_buildheap_complexity.png 1420w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_buildheap_complexity-224x61.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_buildheap_complexity-336x91.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_buildheap_complexity-504x137.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_buildheap_complexity-672x183.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_buildheap_complexity-400x109.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_buildheap_complexity-600x163.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_buildheap_complexity-800x217.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_buildheap_complexity-944x257.png 944w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_buildheap_complexity-1200x326.png 1200w\" sizes=\"(max-width: 1420px) 100vw, 1420px\" \/><\/figure>\n<\/div>\n\n\n<p>Da die Komplexit\u00e4t der <code>heapify()<\/code>-Methode, wie oben gezeigt, <em>O(log n)<\/em> ist, ist die Komplexit\u00e4t f\u00fcr die <code>buildHeap()<\/code>-Methode also maximal* <em>O(n log n)<\/em>.<\/p>\n\n\n\n<p class=\"hc-footnote\">* Im \u00fcbern\u00e4chsten Abschnitt werde ich zeigen, dass die Zeitkomplexit\u00e4t der <code>buildHeap()<\/code>-Methode sogar <em>O(n)<\/em> ist. Da dies an der Gesamt-Zeitkomplexit\u00e4t nichts \u00e4ndert, ist es nicht zwingend erforderlich, diese detailliertere Analyse durchzuf\u00fchren.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"gesamt-zeitkomplexitaet-von-heapsort\">Gesamt-Zeitkomplexit\u00e4t von Heapsort<\/h3>\n\n\n\n<p>Die <code>heapify()<\/code>-Funktion wird <em>n-1<\/em> mal aufgerufen. Die Gesamtkomplexit\u00e4t f\u00fcr das Reparieren des Heaps ist also ebenfalls <em>O(n log n)<\/em>.<\/p>\n\n\n\n<p>Beide Teilalgorithmen haben also die gleiche Zeitkomplexit\u00e4t. Es gilt somit:<\/p>\n\n\n\n<p class=\"has-text-align-center has-background\" style=\"background-color:#e7f2f8\">Die Zeitkomplexit\u00e4t von Heapsort betr\u00e4gt: <em>O(n log n)<\/em><\/p>\n\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"zeitkomplexitaet-fuer-den-aufbau-des-heaps-genauer-analysiert\">Zeitkomplexit\u00e4t f\u00fcr den Aufbau des Heaps \u2013 genauer analysiert<\/h3>\n\n\n\n<p>Dieser Abschnitt ist sehr mathematisch und f\u00fcr die Herleitung der Zeitkomplexit\u00e4t des Gesamtalgorithmus (die wir ja bereits abgeschlossen haben) nicht zwingend erforderlich. Du kannst diesen Abschnitt daher auch \u00fcberspringen.<\/p>\n\n\n\n<p>Wir haben oben festgestellt, dass die <code>buildHeap()<\/code>-Methode f\u00fcr jeden Elternknoten <code>heapify()<\/code> aufruft. Was wir bisher nicht ber\u00fccksichtigt haben ist, dass die Tiefe der Teilb\u00e4ume, auf denen <code>heapify()<\/code> aufgerufen wird, unterschiedlich ist. Folgende Grafik soll das verdeutlichen (<em>d<\/em> steht f\u00fcr die Tiefe der Teilb\u00e4ume):<\/p>\n\n\n<div class=\"wp-block-image hc-image-margins\">\n<figure class=\"aligncenter size-full is-resized\"><img decoding=\"async\" width=\"1564\" height=\"386\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_buildheap_complexity_tree-v2.png\" alt=\"Heapsort-Zeitkomplexit\u00e4t: heapify()-Aufrufe mit Baumtiefe\" class=\"wp-image-15434\" style=\"width:782px;height:193px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_buildheap_complexity_tree-v2.png 1564w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_buildheap_complexity_tree-v2-224x55.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_buildheap_complexity_tree-v2-336x83.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_buildheap_complexity_tree-v2-504x124.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_buildheap_complexity_tree-v2-672x166.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_buildheap_complexity_tree-v2-400x99.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_buildheap_complexity_tree-v2-600x148.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_buildheap_complexity_tree-v2-800x197.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_buildheap_complexity_tree-v2-944x233.png 944w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_buildheap_complexity_tree-v2-1200x296.png 1200w\" sizes=\"(max-width: 1564px) 100vw, 1564px\" \/><\/figure>\n<\/div>\n\n\n<p>Die <code>heapify()<\/code>-Methode wird also maximal f\u00fcr <em>n\/4<\/em> B\u00e4ume der Tiefe <em>1<\/em> aufgerufen, f\u00fcr <em>n\/8<\/em> B\u00e4ume der Tiefe <em>2<\/em>, f\u00fcr <em>n\/16<\/em> B\u00e4ume der Tiefe <em>3<\/em>, usw.<\/p>\n\n\n\n<p>Die maximale Anzahl der Tauschoperationen in der <code>heapify()<\/code>-Methode entspricht der Tiefe des Teilbaums, auf der diese aufgerufen wird.<\/p>\n\n\n\n<p>Die maximale Anzahl der Tauschoperationen <em>S<sub>max<\/sub><\/em> (<em>S<\/em> steht f\u00fcr \"Swap\") f\u00fcr den Aufbau des Heaps betr\u00e4gt somit:<\/p>\n\n\n\n<p class=\"has-text-align-center\"><em>S<sub>max<\/sub> = n\/4 \u00b7 1 + n\/8 \u00b7 2 + n\/16 \u00b7 3 + n\/32 \u00b7 4 + ...<\/em><\/p>\n\n\n\n<p>Wenn wir beide Seiten des Terms mit <em>2<\/em> multiplizieren, erhalten wir:<\/p>\n\n\n\n<p class=\"has-text-align-center\"><em>2 \u00b7 S<sub>max<\/sub> = n\/2 \u00b7 1 + n\/4 \u00b7 2 + n\/8 \u00b7 3 + n\/16 \u00b7 4 + ...<\/em><\/p>\n\n\n\n<p>Legen wir einmal beide Terme \u00fcbereinander:<\/p>\n\n\n\n<figure class=\"wp-block-table aligncenter hc-formular\"><table><tbody><tr><td class=\"has-text-align-right\" data-align=\"right\"><em>2 \u00b7 S<sub>max<\/sub> =<\/em><\/td><td><em>&nbsp;n\/2 \u00b7 1 +&nbsp;<\/em><\/td><td><em>n\/4 \u00b7 2 + n\/8 \u00b7 3 + n\/16 \u00b7 4 + ...<\/em><\/td><\/tr><tr><td class=\"has-text-align-right\" data-align=\"right\"><em>S<sub>max<\/sub> =<\/em><\/td><td><\/td><td><em>n\/4 \u00b7 1 + n\/8 \u00b7 2 + n\/16 \u00b7 3 + n\/32 \u00b7 4 + ...<\/em><\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<p>Beide Terme enthalten <em>n\/4<\/em>, <em>n\/8<\/em>, <em>n\/16<\/em> usw. mit jeweils einem um die Konstante <em>1<\/em> unterschiedlichen Faktor. Wenn wir die Terme subtrahieren, erhalten wir:<\/p>\n\n\n\n<p class=\"has-text-align-center\"><em>2 \u00b7 S<sub>max<\/sub> - S<sub>max<\/sub> = n\/2 \u00b7 1 + n\/4 \u00b7 (2 - 1) + n\/8 \u00b7 (3 - 2) + n\/16 \u00b7 (4 - 3) + ...<\/em><\/p>\n\n\n\n<p>Das l\u00e4sst sich vereinfachen zu:<\/p>\n\n\n\n<p class=\"has-text-align-center\"><em>S<sub>max<\/sub> = n\/2 + n\/4 + n\/8 + n\/16 + ...<\/em><\/p>\n\n\n\n<p>Bzw:<\/p>\n\n\n\n<p class=\"has-text-align-center\"><em>S<sub>max<\/sub> = n \u00b7 (1\/2 + 1\/4 + 1\/8 + 1\/16 + ...)<\/em><\/p>\n\n\n\n<p>Der Term <em>1\/2 + 1\/4 + 1\/8 + 1\/16 + ...<\/em> n\u00e4hert sich an <em>1<\/em> an, wie folgende Darstellung zeigt:<\/p>\n\n\n<div class=\"wp-block-image hc-image-margins\">\n<figure class=\"aligncenter size-full is-resized\"><img decoding=\"async\" width=\"457\" height=\"457\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_circle_v3.png\" alt=\"1\/2 + 1\/4 + 1\/8 + 1\/16 + 1\/32\" class=\"wp-image-15419\" style=\"width:229px;height:229px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_circle_v3.png 457w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_circle_v3-224x224.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_circle_v3-336x336.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_circle_v3-400x400.png 400w\" sizes=\"(max-width: 457px) 100vw, 457px\" \/><\/figure>\n<\/div>\n\n\n<p>Somit l\u00e4sst sich die Formel abschlie\u00dfend vereinfachen auf:<\/p>\n\n\n\n<p class=\"has-text-align-center\">     <em>S<sub>max<\/sub> \u2264 n<\/em><\/p>\n\n\n\n<p>Damit haben wir gezeigt, dass der Aufwand f\u00fcr den Aufbau des Heaps linear ist, die Zeitkomplexit\u00e4t also <em>O(n)<\/em> betr\u00e4gt.<\/p>\n\n\n\n<p>Die oben genannte Gesamtkomplexit\u00e4t von <em>O(n log n)<\/em> \u00e4ndert sich durch die niedrigere Komplexit\u00e4tsklasse eines Teilalgorithmus nicht.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"laufzeit-des-java-heapsort-beispiels\">Laufzeit des Java Heapsort Beispiels<\/h3>\n\n\n\n<p>Mit der Klasse <a rel=\"noopener\" href=\"https:\/\/github.com\/SvenWoltmann\/sorting-algorithms-ultimate-guide\/blob\/main\/src\/main\/java\/eu\/happycoders\/sort\/demos\/UltimateTest.java\" target=\"_blank\">UltimateSort<\/a> kann die Laufzeit verschiedener Sortieralgorithmen f\u00fcr unterschiedliche Eingabegr\u00f6\u00dfen ermittelt werden.<\/p>\n\n\n\n<p>Die folgende Tabelle zeigt die Mediane der Laufzeiten f\u00fcr das Sortieren von zuf\u00e4llig angeordneten, sowie aufsteigend und absteigend vorsortierten Elementen, nach 50 Wiederholungen (dies ist der \u00dcbersicht halber nur ein Auszug; das vollst\u00e4ndige Ergebnis&nbsp;<a href=\"https:\/\/github.com\/SvenWoltmann\/sorting-algorithms-ultimate-guide\/blob\/main\/results\/2020-08-13\/UltimateTest_Heapsort.log\" target=\"_blank\" rel=\"noopener\">findest du hier<\/a>):<\/p>\n\n\n\n<figure class=\"wp-block-table is-style-stripes\"><table><thead><tr><th class=\"has-text-align-right\" data-align=\"right\">n<\/th><th class=\"has-text-align-right\" data-align=\"right\">unsortiert<\/th><th class=\"has-text-align-right\" data-align=\"right\">aufsteigend<\/th><th class=\"has-text-align-right\" data-align=\"right\">absteigend<\/th><\/tr><\/thead><tbody><tr><td class=\"has-text-align-right\" data-align=\"right\">...<\/td><td class=\"has-text-align-right\" data-align=\"right\">...<\/td><td class=\"has-text-align-right\" data-align=\"right\">...<\/td><td class=\"has-text-align-right\" data-align=\"right\">...<\/td><\/tr><tr><td class=\"has-text-align-right\" data-align=\"right\">2.097.152<\/td><td class=\"has-text-align-right\" data-align=\"right\">369,5 ms<\/td><td class=\"has-text-align-right\" data-align=\"right\">198,8 ms<\/td><td class=\"has-text-align-right\" data-align=\"right\">198,8 ms<\/td><\/tr><tr><td class=\"has-text-align-right\" data-align=\"right\">4.194.304<\/td><td class=\"has-text-align-right\" data-align=\"right\">870,2 ms<\/td><td class=\"has-text-align-right\" data-align=\"right\">410,4 ms<\/td><td class=\"has-text-align-right\" data-align=\"right\">412,7 ms<\/td><\/tr><tr><td class=\"has-text-align-right\" data-align=\"right\">8.388.608<\/td><td class=\"has-text-align-right\" data-align=\"right\">2.052,4 ms<\/td><td class=\"has-text-align-right\" data-align=\"right\">848,9 ms<\/td><td class=\"has-text-align-right\" data-align=\"right\">852,9 ms<\/td><\/tr><tr><td class=\"has-text-align-right\" data-align=\"right\">16.777.216<\/td><td class=\"has-text-align-right\" data-align=\"right\">4.686,9 ms<\/td><td class=\"has-text-align-right\" data-align=\"right\">1.752,6 ms<\/td><td class=\"has-text-align-right\" data-align=\"right\">1.775,3 ms<\/td><\/tr><tr><td class=\"has-text-align-right\" data-align=\"right\">33.554.432<\/td><td class=\"has-text-align-right\" data-align=\"right\">10.508,2 ms<\/td><td class=\"has-text-align-right\" data-align=\"right\">3.623,5 ms<\/td><td class=\"has-text-align-right\" data-align=\"right\">3.668,7 ms<\/td><\/tr><tr><td class=\"has-text-align-right\" data-align=\"right\">67.108.864<\/td><td class=\"has-text-align-right\" data-align=\"right\">23.459,9 ms<\/td><td class=\"has-text-align-right\" data-align=\"right\">7.492.4 ms<\/td><td class=\"has-text-align-right\" data-align=\"right\">7.605,5 ms<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<p>Hier die vollst\u00e4ndigen Messwerte als Diagramm:<\/p>\n\n\n<div class=\"wp-block-image hc-img-border-grey\">\n<figure class=\"aligncenter size-full is-resized\"><img decoding=\"async\" width=\"1514\" height=\"868\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_runtime.png\" alt=\"Heapsort runtime for unsorted and sorted elements\" class=\"wp-image-15492\" style=\"width:757px;height:434px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_runtime.png 1514w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_runtime-224x128.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_runtime-336x193.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_runtime-504x289.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_runtime-672x385.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_runtime-400x229.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_runtime-600x344.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_runtime-800x459.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_runtime-944x541.png 944w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_runtime-1200x688.png 1200w\" sizes=\"(max-width: 1514px) 100vw, 1514px\" \/><\/figure>\n<\/div>\n\n\n<p>Es l\u00e4sst sich gut sehen:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Bei Verdopplung der Eingabemenge dauert das Sortieren etwas mehr als doppelt so lange; dies entspricht der erwarteten quasi-linearen Laufzeit <em>O(n log n)<\/em>.<\/li>\n\n\n\n<li>F\u00fcr vorsortierte Eingabedaten ist Heapsort etwa drei mal so schnell wie f\u00fcr unsortierte. <\/li>\n\n\n\n<li>Aufsteigend sortierte Eingabedaten werden etwa gleich schnell sortiert wie absteigend sortierte.<\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"warum-ist-heapsort-fuer-vorsortierte-eingabedaten-schneller\">Warum ist Heapsort f\u00fcr vorsortierte Eingabedaten schneller?<\/h3>\n\n\n\n<p>Um dieser Frage auf den Grund zu gehen, verwende ich das Programm <a rel=\"noopener\" href=\"https:\/\/github.com\/SvenWoltmann\/sorting-algorithms-ultimate-guide\/blob\/main\/src\/main\/java\/eu\/happycoders\/sort\/demos\/CountOperations.java\" target=\"_blank\">CountOperations<\/a>, um die Anzahl von Vergleichs-, Lese- und Schreiboperationen von Heapsort f\u00fcr unsortierte, aufsteigend und absteigend sortierte Daten, f\u00fcr die jeweiligen Phasen, zu messen.<\/p>\n\n\n\n<p>Das Ergebnis findest du in der Datei <a href=\"https:\/\/github.com\/SvenWoltmann\/sorting-algorithms-ultimate-guide\/blob\/main\/results\/2020-08-13\/CountOperations_Heapsort.log\" target=\"_blank\" rel=\"noopener\">CountOperations_Heapsort.log<\/a>. Die Erkenntnisse aus dem Test sind:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Wenn die Eingabedaten absteigend sortiert sind, gibt es in Phase 1 nur etwa halb so viele Vergleiche wie bei unsortierten oder aufsteigend sortierten Daten; au\u00dferdem gibt es keine Tauschoperationen. Dies liegt daran, dass ein absteigend sortiertes Array bereits einem Max Heap entspricht.<\/li>\n\n\n\n<li>Aufsteigend sortierte Eingabedaten hingegeben entsprechen einem Min Heap. Dieser muss in der <code>buildHeap()<\/code>-Phase komplett umgedreht werden, deshalb haben wir in diesem Fall etwa ein Drittel mehr Tauschoperationen als bei zuf\u00e4llig angeordneten Daten, in denen die Heap-Bedingung bereits an einigen Teilb\u00e4umen erf\u00fcllt ist.<\/li>\n\n\n\n<li>In Phase 2 unterscheidet sich die Anzahl der Operationen nur minimal.<\/li>\n<\/ul>\n\n\n\n<p>Wie l\u00e4sst sich dann erkl\u00e4ren, dass Heapsort sowohl f\u00fcr aufsteigend als auch f\u00fcr absteigend vorsortierte Eingabedaten etwa drei mal so schnell ist?<\/p>\n\n\n\n<p>Die Antwort finden wir in der sogenannten <a rel=\"noopener\" href=\"https:\/\/de.wikipedia.org\/wiki\/Sprungvorhersage\" target=\"_blank\">Sprungvorhersage<\/a> (englisch \"branch prediction\").<\/p>\n\n\n\n<p>Bei vorsortierten Eingabedaten f\u00fchren die Vergleichsoperationen immer wieder zum selben Ergebnis. Wenn die Sprungvorhersage nun davon ausgeht, dass die Vergleiche auch in Zukunft zum selben Ergebnis f\u00fchren, k\u00f6nnen die Befehls-Pipelines der CPU voll ausgenutzt werden.<\/p>\n\n\n\n<p>Bei unsortierten Eingabedaten hingegen kann keine zuverl\u00e4ssige Aussage \u00fcber zuk\u00fcnftige Vergleichsergebnisse getroffen werden. Entsprechend muss die Befehls-Pipeline h\u00e4ufig gel\u00f6scht und wieder neu gef\u00fcllt werden.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"bottom-up-heapsort\">Bottom-Up-Heapsort<\/h2>\n\n\n\n<p>Bottom-Up-Heapsort ist eine Variante, bei die <code>heapify()<\/code>-Methode durch geschickte Optimierung mit weniger Vergleichen auskommt. Dies ist vorteilhaft, wenn nicht beispielsweise <code>int<\/code>-Primitive verglichen werden, sondern Objekte mit einer aufw\u00e4ndigen <code>compareTo()<\/code>-Funktion.<\/p>\n\n\n\n<p>Im regul\u00e4ren <code>heapify()<\/code> f\u00fchren wir von oben nach unten an jedem Knoten zwei Vergleiche aus, um das gr\u00f6\u00dfte von drei Elementen zu finden:<\/p>\n\n\n\n<ol class=\"wp-block-list\">\n<li>Elternknoten mit linkem Kind<\/li>\n\n\n\n<li>Der gr\u00f6\u00dfere Knoten aus dem ersten Vergleich mit dem zweiten Kind<\/li>\n<\/ol>\n\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"bottom-up-heapsort-algorithmus\">Bottom-Up-Heapsort Algorithmus<\/h3>\n\n\n\n<p>Bottom-Up-Heapsort hingegen vergleicht nur die zwei Kinder miteinander und folgt dem jeweils gr\u00f6\u00dferen Kind bis zum Ende des Baumes (\"top-down\"). Von dort geht der Algorithmus wieder zur\u00fcck Richtung Baumwurzel (\"bottom-up\") und sucht das erste Element, das gr\u00f6\u00dfer als die Wurzel ist. Von hier ab werden alle Elemente jeweils um eine Position Richtung Wurzel verschoben, und das Wurzelelement wird auf das freigewordene Feld gesetzt.<\/p>\n\n\n\n<p>Das folgendes Beispiel soll das Verst\u00e4ndnis erleichern.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"bottom-up-heapsort-beispiel\">Bottom-Up-Heapsort Beispiel<\/h3>\n\n\n\n<p>In folgendem Beispiel werden die 9 und 4 verglichen, dann die Kinder der 9 \u2013 die 8 und die 6, und zuletzt die Kinder der 8 \u2013 die 7 und die 3:<\/p>\n\n\n<div class=\"wp-block-image hc-image-margins\">\n<figure class=\"aligncenter size-full is-resized\"><img decoding=\"async\" width=\"688\" height=\"412\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/bottom-up-heapsort-1.png\" alt=\"Bottom-up Heapsort - Vergleiche Top-Down\" class=\"wp-image-15568\" style=\"width:344px;height:206px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/bottom-up-heapsort-1.png 688w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/bottom-up-heapsort-1-224x134.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/bottom-up-heapsort-1-336x201.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/bottom-up-heapsort-1-504x302.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/bottom-up-heapsort-1-672x402.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/bottom-up-heapsort-1-400x240.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/bottom-up-heapsort-1-600x359.png 600w\" sizes=\"(max-width: 688px) 100vw, 688px\" \/><\/figure>\n<\/div>\n\n\n<p>Wir erreichen auf diese Weise die 7 und vergleichen diese mit der Baumwurzel, der 5:<\/p>\n\n\n<div class=\"wp-block-image hc-image-margins\">\n<figure class=\"aligncenter size-full is-resized\"><img decoding=\"async\" width=\"688\" height=\"412\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/bottom-up-heapsort-2.png\" alt=\"Bottom-up Heapsort - Vergleiche Bottom-Up\" class=\"wp-image-15569\" style=\"width:344px;height:206px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/bottom-up-heapsort-2.png 688w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/bottom-up-heapsort-2-224x134.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/bottom-up-heapsort-2-336x201.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/bottom-up-heapsort-2-504x302.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/bottom-up-heapsort-2-672x402.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/bottom-up-heapsort-2-400x240.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/bottom-up-heapsort-2-600x359.png 600w\" sizes=\"(max-width: 688px) 100vw, 688px\" \/><\/figure>\n<\/div>\n\n\n<p>Die 5 ist kleiner als die 7. Das bedeutet, dass das Wurzelelement bis ganz nach unten durchgereicht werden muss:<\/p>\n\n\n<div class=\"wp-block-image hc-image-margins\">\n<figure class=\"aligncenter size-full is-resized\"><img decoding=\"async\" width=\"796\" height=\"412\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/bottom-up-heapsort-3.png\" alt=\"Bottom-up Heapsort - Wurzelelement wandert nach unten\" class=\"wp-image-15570\" style=\"width:398px;height:206px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/bottom-up-heapsort-3.png 796w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/bottom-up-heapsort-3-224x116.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/bottom-up-heapsort-3-336x174.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/bottom-up-heapsort-3-504x261.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/bottom-up-heapsort-3-672x348.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/bottom-up-heapsort-3-400x207.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/bottom-up-heapsort-3-600x311.png 600w\" sizes=\"(max-width: 796px) 100vw, 796px\" \/><\/figure>\n<\/div>\n\n\n<p>Im Endeffekt f\u00fchrt dies zum gleichen Ergebnis wie das regul\u00e4re <code>heapify()<\/code>.<\/p>\n\n\n\n<p>Bottom-Up-Heapsort macht sich zunutze, dass das Wurzelelement in der Regel sehr weit nach unten geschoben wird, da dieses nach jeder Iteration vom Ende des Baumes kommt und daher relativ klein ist.<\/p>\n\n\n\n<p>Somit sind weniger Vergleiche n\u00f6tig, wenn einmal bis ganz nach unten verglichen wird und dann wieder ein kurzes St\u00fcck nach oben, als wenn von oben bis nach ganz unten jeweils zwei Vergleiche durchgef\u00fchrt werden:<\/p>\n\n\n<div class=\"wp-block-image hc-image-margins\">\n<figure class=\"aligncenter size-full is-resized\"><img decoding=\"async\" width=\"1502\" height=\"550\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/bottom-up-heapsort_vs_heapsort.png\" alt=\"Bottom-up Heapsort vs. Regular Heapsort\" class=\"wp-image-15572\" style=\"width:751px;height:275px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/bottom-up-heapsort_vs_heapsort.png 1502w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/bottom-up-heapsort_vs_heapsort-224x82.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/bottom-up-heapsort_vs_heapsort-336x123.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/bottom-up-heapsort_vs_heapsort-504x185.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/bottom-up-heapsort_vs_heapsort-672x246.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/bottom-up-heapsort_vs_heapsort-400x146.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/bottom-up-heapsort_vs_heapsort-600x220.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/bottom-up-heapsort_vs_heapsort-800x293.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/bottom-up-heapsort_vs_heapsort-944x346.png 944w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/bottom-up-heapsort_vs_heapsort-1200x439.png 1200w\" sizes=\"(max-width: 1502px) 100vw, 1502px\" \/><\/figure>\n<\/div>\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"bottom-up-heapsort-quellcode\">Bottom-Up-Heapsort Quellcode<\/h3>\n\n\n\n<p>Die Klasse <a rel=\"noopener\" href=\"https:\/\/github.com\/SvenWoltmann\/sorting-algorithms-ultimate-guide\/blob\/main\/src\/main\/java\/eu\/happycoders\/sort\/method\/heapsort\/BottomUpHeapsort.java\" target=\"_blank\">BottomUpHeapsort<\/a> erbt von <code>Heapsort<\/code> und \u00fcberschreibt lediglich deren <code>heapify()<\/code>-Methode mit der folgenden:<\/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\">void<\/span> <span class=\"hljs-title\">heapify<\/span><span class=\"hljs-params\">(<span class=\"hljs-keyword\">int<\/span>&#091;] heap, <span class=\"hljs-keyword\">int<\/span> length, <span class=\"hljs-keyword\">int<\/span> rootPos)<\/span> <\/span>{\n  <span class=\"hljs-keyword\">int<\/span> leafPos = findLeaf(heap, length, rootPos);\n  <span class=\"hljs-keyword\">int<\/span> nodePos = findTargetNodeBottomUp(heap, rootPos, leafPos);\n\n  <span class=\"hljs-keyword\">if<\/span> (rootPos == nodePos) <span class=\"hljs-keyword\">return<\/span>;\n\n  <span class=\"hljs-comment\">\/\/ Move all elements starting at nodePos to parent, move root to nodePos<\/span>\n  <span class=\"hljs-keyword\">int<\/span> nodeValue = heap&#091;nodePos];\n  heap&#091;nodePos] = heap&#091;rootPos];\n\n  <span class=\"hljs-keyword\">while<\/span> (nodePos &gt; rootPos) {\n    <span class=\"hljs-keyword\">int<\/span> parentPos = getParentPos(nodePos);\n    <span class=\"hljs-keyword\">int<\/span> parentValue = heap&#091;parentPos];\n    heap&#091;parentPos] = nodeValue;\n    nodePos = getParentPos(nodePos);\n    nodeValue = parentValue;\n  }\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>findLeaf()<\/code>-Methode vergleicht jeweils zwei Kinder und folgt dem jeweils gr\u00f6\u00dferen, bis das Ende des Baumes erreicht ist (bzw. ein Knoten, der nur noch <em>ein<\/em> Kind enth\u00e4lt):<\/p>\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\">int<\/span> <span class=\"hljs-title\">findLeaf<\/span><span class=\"hljs-params\">(<span class=\"hljs-keyword\">int<\/span>&#091;] heap, <span class=\"hljs-keyword\">int<\/span> length, <span class=\"hljs-keyword\">int<\/span> rootPos)<\/span> <\/span>{\n  <span class=\"hljs-keyword\">int<\/span> pos = rootPos;\n  <span class=\"hljs-keyword\">int<\/span> leftChildPos = pos * <span class=\"hljs-number\">2<\/span> + <span class=\"hljs-number\">1<\/span>;\n  <span class=\"hljs-keyword\">int<\/span> rightChildPos = pos * <span class=\"hljs-number\">2<\/span> + <span class=\"hljs-number\">2<\/span>;\n\n  <span class=\"hljs-comment\">\/\/ Two child exist?<\/span>\n  <span class=\"hljs-keyword\">while<\/span> (rightChildPos &lt; length) {\n    <span class=\"hljs-keyword\">if<\/span> (heap&#091;rightChildPos] &gt; heap&#091;leftChildPos]) {\n      pos = rightChildPos;\n    } <span class=\"hljs-keyword\">else<\/span> {\n      pos = leftChildPos;\n    }\n    leftChildPos = pos * <span class=\"hljs-number\">2<\/span> + <span class=\"hljs-number\">1<\/span>;\n    rightChildPos = pos * <span class=\"hljs-number\">2<\/span> + <span class=\"hljs-number\">2<\/span>;\n  }\n\n  <span class=\"hljs-comment\">\/\/ One child exist?<\/span>\n  <span class=\"hljs-keyword\">if<\/span> (leftChildPos &lt; length) {\n    pos = leftChildPos;\n  }\n\n  <span class=\"hljs-keyword\">return<\/span> pos;\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>Die Methode <code>findTargetNodeBottomUp()<\/code> sucht von unten nach oben das erste Element, das nicht kleiner als der Wurzelknoten ist:<\/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-function\"><span class=\"hljs-keyword\">int<\/span> <span class=\"hljs-title\">findTargetNodeBottomUp<\/span><span class=\"hljs-params\">(<span class=\"hljs-keyword\">int<\/span>&#091;] heap, <span class=\"hljs-keyword\">int<\/span> rootPos, <span class=\"hljs-keyword\">int<\/span> leafPos)<\/span> <\/span>{\n  <span class=\"hljs-keyword\">int<\/span> parent = heap&#091;rootPos];\n  <span class=\"hljs-keyword\">while<\/span> (leafPos != rootPos &amp;&amp; heap&#091;leafPos] &lt; parent) {\n    leafPos = getParentPos(leafPos);\n  }\n  <span class=\"hljs-keyword\">return<\/span> leafPos;\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<p>Und zuletzt die <code>getParentPos()<\/code>-Methode:<\/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\">int<\/span> <span class=\"hljs-title\">getParentPos<\/span><span class=\"hljs-params\">(<span class=\"hljs-keyword\">int<\/span> pos)<\/span> <\/span>{\n  <span class=\"hljs-keyword\">return<\/span> (pos - <span class=\"hljs-number\">1<\/span>) \/ <span class=\"hljs-number\">2<\/span>;\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<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"bottom-up-heapsort-performance\">Bottom-Up-Heapsort Performance<\/h3>\n\n\n\n<p>Die Performance von Bottom-Up-Heapsort kann ebenfalls mit dem <a rel=\"noopener\" href=\"https:\/\/github.com\/SvenWoltmann\/sorting-algorithms-ultimate-guide\/blob\/main\/src\/main\/java\/eu\/happycoders\/sort\/demos\/UltimateTest.java\" target=\"_blank\">UltimateTest<\/a> gemessen werden. Die Messwerte findest Du in ebenfalls in <a rel=\"noopener\" href=\"https:\/\/github.com\/SvenWoltmann\/sorting-algorithms-ultimate-guide\/blob\/main\/results\/2020-08-13\/UltimateTest_Heapsort.log\" target=\"_blank\">UltimateTest_Heapsort.log<\/a>. Das folgende Diagramm zeigt die Laufzeiten von Bottom-Up-Heapsort im Vergleich mit dem regul\u00e4ren Heapsort:<\/p>\n\n\n<div class=\"wp-block-image hc-img-border-grey\">\n<figure class=\"aligncenter size-full is-resized\"><img decoding=\"async\" width=\"1514\" height=\"868\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_vs_bottom-up-heapsort.png\" alt=\"Laufzeiten von Heapsort und Bottom-Up-Heapsort\" class=\"wp-image-15495\" style=\"width:757px;height:434px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_vs_bottom-up-heapsort.png 1514w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_vs_bottom-up-heapsort-224x128.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_vs_bottom-up-heapsort-336x193.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_vs_bottom-up-heapsort-504x289.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_vs_bottom-up-heapsort-672x385.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_vs_bottom-up-heapsort-400x229.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_vs_bottom-up-heapsort-600x344.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_vs_bottom-up-heapsort-800x459.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_vs_bottom-up-heapsort-944x541.png 944w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_vs_bottom-up-heapsort-1200x688.png 1200w\" sizes=\"(max-width: 1514px) 100vw, 1514px\" \/><\/figure>\n<\/div>\n\n\n<p>Wie man sieht ben\u00f6tigt Bottom-Up-Heapsort f\u00fcr unsortierte Daten bis zu doppelt so lange wie das regul\u00e4re Heapsort, w\u00e4hrend es bei sortierten Daten in etwa gleich schnell ist.<\/p>\n\n\n\n<p>Bevor wir der Ursache daf\u00fcr auf den Grund gehen, schauen wir uns zun\u00e4chst einen kleineren Ausschnitt des Diagramms an:<\/p>\n\n\n<div class=\"wp-block-image hc-img-border-grey\">\n<figure class=\"aligncenter size-full is-resized\"><img decoding=\"async\" width=\"1514\" height=\"868\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_vs_bottom-up-heapsort-low-n.png\" alt=\"Laufzeiten von Heapsort und Bottom-Up-Heapsort f\u00fcr kleine n\" class=\"wp-image-15592\" style=\"width:757px;height:434px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_vs_bottom-up-heapsort-low-n.png 1514w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_vs_bottom-up-heapsort-low-n-224x128.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_vs_bottom-up-heapsort-low-n-336x193.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_vs_bottom-up-heapsort-low-n-504x289.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_vs_bottom-up-heapsort-low-n-672x385.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_vs_bottom-up-heapsort-low-n-400x229.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_vs_bottom-up-heapsort-low-n-600x344.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_vs_bottom-up-heapsort-low-n-800x459.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_vs_bottom-up-heapsort-low-n-944x541.png 944w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_vs_bottom-up-heapsort-low-n-1200x688.png 1200w\" sizes=\"(max-width: 1514px) 100vw, 1514px\" \/><\/figure>\n<\/div>\n\n\n<p>Bottom-Up-Heapsort wird also erst ab etwa zwei Millionen Elementen langsamer als das regul\u00e4re Heapsort.<\/p>\n\n\n\n<p>Worin liegt die Ursache?<\/p>\n\n\n\n<p>Das <a rel=\"noopener\" href=\"https:\/\/github.com\/SvenWoltmann\/sorting-algorithms-ultimate-guide\/blob\/main\/results\/2020-08-13\/CountOperations_Heapsort.log\" target=\"_blank\">Ergebnis des oben erw\u00e4hnten CountOperations<\/a>-Programms zeigt, dass Bottom-Up-Heapsort weniger Vergleichs-, Lese und Schreiboperationen ben\u00f6tigt als das regul\u00e4re Heapsort \u2013 und zwar unabh\u00e4ngig von der Anzahl der zu sortierenden Elemente.<\/p>\n\n\n\n<p>Warum ist es dennoch langsamer?<\/p>\n\n\n\n<p>Bottom-up-Heapsort basiert auf der Annahme, dass das Wurzelelement immer bis zur Blattebene verschoben wird. Diese Annahme kann sich auch die Sprungvorhersage der CPU zunutze machen und damit diesen Vorteil relativieren.<\/p>\n\n\n\n<p>Des weiteren m\u00fcssen wir bei Bottom-Up-Heapsort zweimal durch den Baum gehen: einmal von oben nach unten und einmal zur\u00fcck nach oben. Dies wirkt sich zwar nicht negativ auf die Anzahl der Operation aus, wohl aber auf den Zugriff auf den Hauptspeicher!<\/p>\n\n\n\n<p>Denn w\u00e4hrend beim einmaligen Traversieren des Baumes Speicherseiten nur einmal vom Hauptspeicher in den CPU-Cache geladen werden m\u00fcssen, sind bei entsprechend gro\u00dfen B\u00e4umen auf dem R\u00fcckweg die meisten Speicherseiten bereits wieder aus dem Cache entfernt und m\u00fcssen erneut gelesen werden.<\/p>\n\n\n\n<p>Daher n\u00e4hern wir uns bei hinreichend gro\u00dfen B\u00e4umen an den Geschwindigkeitsfaktor zwei an.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"bottom-up-heapsort-mit-teuren-vergleichsoperationen\">Bottom-Up-Heapsort mit teuren Vergleichsoperationen<\/h3>\n\n\n\n<p>Bottom-Up-Heapsort optimiert dahingehend, dass weniger Vergleiche ausgef\u00fchrt werden m\u00fcssen. Bei <code>int<\/code>-Primitiven fallen Vergleiche nicht ins Gewicht, daher kann Bottom-Up-Heapsort hier seine Vorteile nicht ausspielen.<\/p>\n\n\n\n<p>Ich habe daher einen weiteren Test ausgef\u00fchrt, indem ich die Vergleichsoperationen k\u00fcnstlich verteuert habe. Du findest die angepassten Algorithmen in den Klassen <a rel=\"noopener\" href=\"https:\/\/github.com\/SvenWoltmann\/sorting-algorithms-ultimate-guide\/blob\/main\/src\/main\/java\/eu\/happycoders\/sort\/method\/heapsort\/HeapsortSlowComparisons.java\" target=\"_blank\">HeapsortSlowComparisons<\/a> und <a rel=\"noopener\" href=\"https:\/\/github.com\/SvenWoltmann\/sorting-algorithms-ultimate-guide\/blob\/main\/src\/main\/java\/eu\/happycoders\/sort\/method\/heapsort\/BottomUpHeapsortSlowComparisons.java\" target=\"_blank\">BottomUpHeapsortSlowComparisons<\/a> im GitHub-Repository.<\/p>\n\n\n\n<p>Bottom-Up-Heapsort schneidet bei diesem Vergleich deutlich besser ab:<\/p>\n\n\n<div class=\"wp-block-image hc-img-border-grey\">\n<figure class=\"aligncenter size-full is-resized\"><img decoding=\"async\" width=\"1514\" height=\"868\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_vs_bottom-up-heapsort-slow-comparisons.png\" alt=\"Laufzeiten von Heapsort und Bottom-Up Heapsort mit teuren Vergleichsoperationen\" class=\"wp-image-15496\" style=\"width:757px;height:434px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_vs_bottom-up-heapsort-slow-comparisons.png 1514w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_vs_bottom-up-heapsort-slow-comparisons-224x128.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_vs_bottom-up-heapsort-slow-comparisons-336x193.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_vs_bottom-up-heapsort-slow-comparisons-504x289.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_vs_bottom-up-heapsort-slow-comparisons-672x385.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_vs_bottom-up-heapsort-slow-comparisons-400x229.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_vs_bottom-up-heapsort-slow-comparisons-600x344.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_vs_bottom-up-heapsort-slow-comparisons-800x459.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_vs_bottom-up-heapsort-slow-comparisons-944x541.png 944w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_vs_bottom-up-heapsort-slow-comparisons-1200x688.png 1200w\" sizes=\"(max-width: 1514px) 100vw, 1514px\" \/><\/figure>\n<\/div>\n\n\n<h2 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"weitere-eigenschaften-von-heapsort\">Weitere Eigenschaften von Heapsort<\/h2>\n\n\n\n<p>Im folgenden werden die Platzkomplexit\u00e4t von Heapsort, dessen Stabilit\u00e4t und Parallelisierbarkeit betrachtet.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"platzkomplexitaet-von-heapsort\">Platzkomplexit\u00e4t von Heapsort<\/h3>\n\n\n\n<p>Heapsort ist ein In-Place-Sortierverfahren, d. h. au\u00dfer f\u00fcr Schleifen- und Hilfsvariablen wird kein zus\u00e4tzlicher Speicherplatz ben\u00f6tigt. Die Anzahl dieser Variablen ist immer gleich, egal ob wir zehn Elemente sortieren oder zehn Millionen. Daher gilt:<\/p>\n\n\n\n<p class=\"has-text-align-center has-background\" style=\"background-color:#e7f2f8\">Die Platzkomplexit\u00e4t von Heapsort ist: <em>O(1)<\/em><\/p>\n\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"stabilitaet-von-heapsort\">Stabilit\u00e4t von Heapsort<\/h3>\n\n\n\n<p>Es lassen sich sehr leicht Beispiele konstruieren, die zeigen, dass Elemente mit gleichem Key ihre Position zueinander \u00e4ndern k\u00f6nnen:<\/p>\n\n\n\n<h4 class=\"wp-block-heading\">Beispiel 1<\/h4>\n\n\n\n<p>Wenn wir das Array <em>[3, 2a, 2b, 1]<\/em> mit Heapsort sortieren, sehen die Schritte wie folgt aus (<em>2a<\/em> und <em>2b<\/em> stellen zwei Elemente mit demselben Key dar; hellgelb markiert sind die Elemente, die im n\u00e4chsten Schritt vertauscht werden; blau markiert sind fertig sortierte Elemente):<\/p>\n\n\n\n<figure class=\"wp-block-image size-full is-resized hc-image-margins\"><img decoding=\"async\" width=\"1546\" height=\"464\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_not_stable_1-v2.png\" alt=\"Heapsort ist nicht stabil, Beispiel 1\" class=\"wp-image-15507\" style=\"width:773px;height:232px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_not_stable_1-v2.png 1546w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_not_stable_1-v2-224x67.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_not_stable_1-v2-336x101.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_not_stable_1-v2-504x151.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_not_stable_1-v2-672x202.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_not_stable_1-v2-400x120.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_not_stable_1-v2-600x180.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_not_stable_1-v2-800x240.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_not_stable_1-v2-944x283.png 944w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_not_stable_1-v2-1200x360.png 1200w\" sizes=\"(max-width: 1546px) 100vw, 1546px\" \/><\/figure>\n\n\n\n<p>An dieser Stelle k\u00f6nnen wir abbrechen, denn wir sehen bereits jetzt, dass das Ziel-Array auf <em>[2a, 3]<\/em> enden wird, d. h. die <em>2a<\/em> wird rechts neben der <em>2b<\/em> im Ziel-Array landen.<\/p>\n\n\n\n<h4 class=\"wp-block-heading\">Algorithmus anpassen?<\/h4>\n\n\n\n<p>Im zweiten Schritt haben wir entsprechend des Algorithmus die <em>1<\/em> mit der <em>2a<\/em> vertauscht. K\u00f6nnten wir den Algorithmus so \u00e4ndern, dass bei Kindknoten mit gleichem Key, nicht mit dem linken Kind getauscht wird, sondern mit dem rechten? <\/p>\n\n\n\n<p>In dem Fall w\u00fcrde das Array oben stabil sortiert werden, da die <em>1<\/em> nicht mit der <em>2a<\/em>, sondern mit der <em>2b<\/em> getauscht werden w\u00fcrde, und daraufhin die <em>2b<\/em> an der vorletzte Stelle des Arrays landen w\u00fcrde.<\/p>\n\n\n\n<h4 class=\"wp-block-heading\">Beispiel 2<\/h4>\n\n\n\n<p>Versuchen wir das einmal mit einem anderen Eingabearray, mit <em>[4, 3, 2a, 2b, 1]<\/em>:<\/p>\n\n\n\n<figure class=\"wp-block-image size-full is-resized hc-image-margins\"><img decoding=\"async\" width=\"1546\" height=\"910\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_not_stable_2.png\" alt=\"Heapsort ist nicht stabil, Beispiel 2\" class=\"wp-image-15508\" style=\"width:773px;height:455px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_not_stable_2.png 1546w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_not_stable_2-224x132.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_not_stable_2-336x198.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_not_stable_2-504x297.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_not_stable_2-672x396.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_not_stable_2-400x235.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_not_stable_2-600x353.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_not_stable_2-800x471.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_not_stable_2-944x556.png 944w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_not_stable_2-1200x706.png 1200w\" sizes=\"(max-width: 1546px) 100vw, 1546px\" \/><\/figure>\n\n\n\n<p>Nach Schritt 2 wurde der Stand erreicht, den wir zuvor als Ausgangsarray hatten, wobei jedoch <em>2a<\/em> und <em>2b<\/em> ihre Positionen getauscht haben. Wenn wir im n\u00e4chsten Schritt die <em>1<\/em> nun mit dem rechten Kind tauschen, passiert das gleiche wie oben: die <em>2a<\/em> landet zuerst im Ziel-Array und damit rechts von der <em>2b<\/em>.<\/p>\n\n\n\n<p>Wir haben f\u00fcr beide Algorithmus-Varianten Gegenbeispiele gezeigt und k\u00f6nnen daher feststellen:<\/p>\n\n\n\n<p class=\"has-text-align-center has-background\" style=\"background-color:#e7f2f8\">Heapsort ist kein stabiles Sortierverfahren.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"parallelisierbarkeit-von-heapsort\">Parallelisierbarkeit von Heapsort<\/h3>\n\n\n\n<p>Bei Heapsort wird das gesamte Array st\u00e4ndig ver\u00e4ndert, so dass es keine naheliegenden L\u00f6sungen gibt den Algororithmus zu parallelisieren.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"vergleich-von-heapsort-mit-anderen-effizienten-sortierverfahren\">Vergleich von Heapsort mit anderen effizienten Sortierverfahren<\/h2>\n\n\n\n<p>Im folgenden Diagramm siehst du die Ergebnisse des UltimateTests von Heapsort im Vergleich zu den Messwerten von <a href=\"\/de\/algorithmen\/quicksort\/\">Quicksort<\/a> und <a href=\"\/de\/algorithmen\/mergesort\/\">Mergesort<\/a> (im englischen in der Regel \"Merge Sort\") aus den jeweiligen Artikeln:<\/p>\n\n\n<div class=\"wp-block-image hc-img-border-grey\">\n<figure class=\"aligncenter size-full is-resized\"><img decoding=\"async\" width=\"1514\" height=\"896\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_vs_quicksort_vs_mergesort-v2.png\" alt=\"Laufzeiten von Heapsort, Quicksort und Mergesort\" class=\"wp-image-15584\" style=\"width:757px;height:448px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_vs_quicksort_vs_mergesort-v2.png 1514w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_vs_quicksort_vs_mergesort-v2-224x133.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_vs_quicksort_vs_mergesort-v2-336x199.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_vs_quicksort_vs_mergesort-v2-504x298.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_vs_quicksort_vs_mergesort-v2-672x398.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_vs_quicksort_vs_mergesort-v2-400x237.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_vs_quicksort_vs_mergesort-v2-600x355.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_vs_quicksort_vs_mergesort-v2-800x473.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_vs_quicksort_vs_mergesort-v2-944x559.png 944w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heapsort_vs_quicksort_vs_mergesort-v2-1200x710.png 1200w\" sizes=\"(max-width: 1514px) 100vw, 1514px\" \/><\/figure>\n<\/div>\n\n\n<p>Heapsort ist bei zuf\u00e4llig verteilten Eingabedaten um Faktor 3,6 langsamer als Quicksort und um Faktor 2,4 langsamer als Merge Sort. Bei sortierten Daten ist Heapsort um Faktor 8 bis 9 langsamer als Quicksort und um Faktor 2 langsamer als Merge Sort.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"heapsort-vs-quicksort\">Heapsort vs. Quicksort<\/h3>\n\n\n\n<p>Wie im vorangegangenen Abschnitt gezeigt, ist Quicksort in der Regel deutlich schneller als Heapsort.<\/p>\n\n\n\n<p>Aufgrund der <em>worst-case<\/em> Zeitkomplexit\u00e4t bei Quicksort von <em>O(n\u00b2)<\/em> wird in der Praxis in manchen F\u00e4llen Heapsort gegen\u00fcber Quicksort vorgezogen. <\/p>\n\n\n\n<p>Wie im <a href=\"\/de\/algorithmen\/quicksort\/\">Artikel \u00fcber Quicksort<\/a> gezeigt, ist bei geeigneter Wahl des Pivot-Elements der Eintritt des <em>worst cases<\/em> unwahrscheinlich. Dennoch besteht ein gewisses Risiko, welches ein potentieller Angreifer mit ausreichend Kenntnis der verwendeten Quicksort-Implementierung ausnutzen kann, um eine Anwendung mit entsprechend pr\u00e4parierten Eingabedaten in die Knie zu zwingen.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"heapsort-vs-mergesort\">Heapsort vs. Mergesort<\/h3>\n\n\n\n<p>Auch Mergesort ist in der Regel schneller als Heapsort. Au\u00dferdem ist Mergesort im Gegensatz zu Heapsort stabil.<\/p>\n\n\n\n<p>Heapsort hat gegen\u00fcber Mergesort den Vorteil, dass es keinen zus\u00e4tzlichen Speicherbedarf hat, w\u00e4hrend Mergesort zus\u00e4tzlichen Speicher in der Gr\u00f6\u00dfenordnung <em>O(n)<\/em> ben\u00f6tigt.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"zusammenfassung\">Zusammenfassung<\/h2>\n\n\n\n<p>Heapsort ist ein effizienter, nicht stabiler Sortieralgorithmus mit einer Zeitkomplexit\u00e4t von&nbsp;<em>O(n log n)<\/em>&nbsp;im&nbsp;<em>average<\/em>, <em>best<\/em> und <em>worst case<\/em>.<\/p>\n\n\n\n<p>Heapsort ist deutlich langsamer als Quicksort und Mergesort, weshalb man Heapsort in der Praxis seltener antrifft.<\/p>\n\n\n\n<p>Weitere Sortieralgorithmen findest du in der&nbsp;<a href=\"https:\/\/www.happycoders.eu\/de\/algorithmen\/sortieralgorithmen\/#Vergleich_der_wichtigsten_Sortieralgorithmen\">\u00dcbersicht aller Sortieralgorithmen und ihrer Eigenschaften<\/a>&nbsp;im ersten Teil der Artikelserie.<\/p>\n<aside><p>Wenn dir der Artikel weitergeholfen hat, w\u00fcrde ich mich sehr \u00fcber eine positive Bewertung auf meinem <a href=\"https:\/\/www.provenexpert.com\/de-de\/sven-woltmann-happycoders-eu\/7smk\/\" target=\"_blank\" rel=\"noopener\">ProvenExpert-Profil<\/a> freuen. Dein Feedback hilft mir, meine Inhalte weiter zu verbessern und motiviert mich, neue informative Artikel zu schreiben.<\/p>\r\n                        <p>\ud83d\udc49 <a href=\"https:\/\/www.provenexpert.com\/de-de\/sven-woltmann-happycoders-eu\/7smk\/\" target=\"_blank\" rel=\"noopener\">Bewertung abgeben<\/a><\/p>\r\n                        <p>M\u00f6chtest du auf dem Laufenden bleiben und informiert werden, wenn neue Artikel auf HappyCoders.eu ver\u00f6ffentlicht werden? Dann <a href=\"#\" data-formkit-toggle=\"d8ee997126\">klicke hier<\/a>, um dich f\u00fcr den HappyCoders-Newsletter anzumelden.<\/p>\r\n                        <p>\ud83d\udc49 <a href=\"#\" data-formkit-toggle=\"d8ee997126\">Newsletter-Anmeldung<\/a><\/p><\/aside>","protected":false},"excerpt":{"rendered":"<p>In diesem Artikel zeige ich dir, das Heapsort nichts mit dem Java-Heap zu tun hat. Ich zeige die Funktionsweise, den Java-Quellcode und erkl\u00e4re, wie man die Zeitkomplexit\u00e4t bestimmt.<\/p>\n","protected":false},"author":1,"featured_media":43252,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_seopress_robots_primary_cat":"none","_seopress_titles_title":"","_seopress_titles_desc":"Wie funktioniert Heapsort? Mit Illustrationen und Quellcode. Wie bestimmt man die Zeitkomplexit\u00e4t (ohne komplizierte Mathematik)?","_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":26181,"_post_count":0,"footnotes":""},"categories":[127],"tags":[129],"class_list":["post-12216","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-algorithmen","tag-sortieralgorithmen"],"uagb_featured_image_src":{"full":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heap-sort-java-feature-image.jpg",1770,986,false],"thumbnail":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heap-sort-java-feature-image.jpg",150,84,false],"medium":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heap-sort-java-feature-image.jpg",300,167,false],"medium_large":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heap-sort-java-feature-image.jpg",768,428,false],"large":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heap-sort-java-feature-image.jpg",1024,570,false],"feature_thumb_224":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heap-sort-java-feature-image-224x125.jpg",224,125,true],"feature_thumb_336":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heap-sort-java-feature-image-336x187.jpg",336,187,true],"feature_thumb_504":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heap-sort-java-feature-image-504x281.jpg",504,281,true],"feature_thumb_672":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heap-sort-java-feature-image-672x374.jpg",672,374,true],"half_400":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heap-sort-java-feature-image-400x223.jpg",400,223,true],"half_600":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heap-sort-java-feature-image-600x334.jpg",600,334,true],"full_800":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heap-sort-java-feature-image-800x446.jpg",800,446,true],"full_944":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heap-sort-java-feature-image-944x526.jpg",944,526,true],"full_1200":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heap-sort-java-feature-image-1200x668.jpg",1200,668,true],"wide_1180":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heap-sort-java-feature-image-1180x490.jpg",1180,490,true],"wide_1770":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heap-sort-java-feature-image-1770x735.jpg",1770,735,true],"1536x1536":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heap-sort-java-feature-image.jpg",1536,856,false],"2048x2048":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/heap-sort-java-feature-image.jpg",1770,986,false]},"uagb_author_info":{"display_name":"Sven Woltmann","author_link":"https:\/\/www.happycoders.eu\/de\/author\/sven\/"},"uagb_comment_info":2,"uagb_excerpt":"In diesem Artikel zeige ich dir, das Heapsort nichts mit dem Java-Heap zu tun hat. Ich zeige die Funktionsweise, den Java-Quellcode und erkl\u00e4re, wie man die Zeitkomplexit\u00e4t bestimmt.","public_identification_id":"7dfeb15384a94275bce460d155491c38","private_identification_id":"60704e1b758a4c1db6eb8b36cf3da228","_links":{"self":[{"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/posts\/12216","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=12216"}],"version-history":[{"count":10,"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/posts\/12216\/revisions"}],"predecessor-version":[{"id":52517,"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/posts\/12216\/revisions\/52517"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/media\/43252"}],"wp:attachment":[{"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/media?parent=12216"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/categories?post=12216"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/tags?post=12216"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}