{"id":55,"date":"2014-11-12T06:00:00","date_gmt":"2014-11-12T11:00:00","guid":{"rendered":"http:\/\/pfsensesetup.com\/pythonscript.net\/?p=55"},"modified":"2014-11-11T20:03:47","modified_gmt":"2014-11-12T01:03:47","slug":"heapsort-part-two","status":"publish","type":"post","link":"http:\/\/pfsensesetup.com\/pythonscript.net\/heapsort-part-two\/","title":{"rendered":"Heapsort: Part Two"},"content":{"rendered":"<p><a href=\"http:\/\/pfsensesetup.com\/pythonscript.net\/wp-content\/uploads\/2014\/10\/Python_logo_by_BlueX_pl.png\"><img loading=\"lazy\" decoding=\"async\" class=\"alignleft size-medium wp-image-26\" src=\"http:\/\/pfsensesetup.com\/pythonscript.net\/wp-content\/uploads\/2014\/10\/Python_logo_by_BlueX_pl-300x300.png\" alt=\"Heapsort\" width=\"300\" height=\"300\" srcset=\"http:\/\/pfsensesetup.com\/pythonscript.net\/wp-content\/uploads\/2014\/10\/Python_logo_by_BlueX_pl-300x300.png 300w, http:\/\/pfsensesetup.com\/pythonscript.net\/wp-content\/uploads\/2014\/10\/Python_logo_by_BlueX_pl-150x150.png 150w, http:\/\/pfsensesetup.com\/pythonscript.net\/wp-content\/uploads\/2014\/10\/Python_logo_by_BlueX_pl.png 600w\" sizes=\"auto, (max-width: 300px) 100vw, 300px\" \/><\/a>In the previous article, we introduced the heapsort algorithm and coded several helper functions in Python. In this article, we will finally code the heapsort function and test it on some input data.<\/p>\n<p>To recap, we already introduced the following functions:<\/p>\n<ul>\n<li>heapify: Turns a list into a binary heap.<\/li>\n<li>rebuildHeap: Accepts as input a heap with the root node deleted and rebuilds the heap.<\/li>\n<li>consolidateHeap: Moves all empty nodes to the bottom of the heap so we can shrink the heap.<\/li>\n<li>swap: Swaps the contents of two variables.<\/li>\n<\/ul>\n<p>Since we did all the heavy lifting in writing the helper functions, coding heapSort is rather simple:<\/p>\n<pre><strong><span style=\"color: #0000ff;\">def heapSort(L):\r\n   '''Given a list, perform a binary sort on it\r\n   '''\r\n   # First, reconstitute list as a binary heap: \r\n   heapify(L)\r\n   high = len(L)\r\n   # While there is still data in the heap,\r\n   # remove the root node, rebuild and\r\n   # consolidate the heap, and move the old\r\n   # root node to the end\r\n   while high &gt; 0:\r\n      # Delete root node; save in temp\r\n      temp = L[0]\r\n      L[0] = None\r\n      # Rebuild and consolidate heap\r\n      rebuildHeap(L,0,high)\r\n      consolidateHeap(L,high)\r\n      high -= 1\r\n      # Move old root node to end\r\n      L[high] = temp\r\n<\/span><\/strong><\/pre>\n<p>As you can see, once we create the heap, all we are doing is [1] deleting the root node from the heap by setting its value to &#8220;None&#8221;; [2] rebuild the heap and consolidate the heap; [3] decrement the variable indicating the size of the heap; [4] move the old root node back into the list right after the heap; [5] repeat until the heap size is 0. You may have noticed that when we call rebuildHeap and consolidateHeap, we specify the size of the heap. This is to ensure the sorted list which we are inserting at the end of the list is not treated as part of the heap.<\/p>\n<p>To test our heapsort function, I reused the list from the previous article, and used the following code:<\/p>\n<p><strong>&gt;&gt;&gt; myList = [123,79,29,997,519,17,239,144,51,372]<\/strong><br \/>\n<strong> &gt;&gt;&gt; heapSort(myList)<\/strong><br \/>\n<strong> &gt;&gt;&gt; print(myList)<\/strong><br \/>\n<strong> [17, 29, 51, 79, 123, 144, 239, 372, 519, 997]<\/strong><\/p>\n<p>As you can see, the heapsort function seems to work, and has the added advantage (over merge sort) of supporting the ability to sort in place. In the next article, we&#8217;ll examine one more efficient sorting algorithm: quicksort.<\/p>\n<p>The source code for this heapsort implementation can be found <a href=\"http:\/\/pythonscript.net\/pythonscripts\/heapsort.py\">here<\/a>.<\/p>\n<h3><span style=\"text-decoration: underline;\"><strong>External Links:<\/strong><\/span><\/h3>\n<p><a href=\"http:\/\/en.wikipedia.org\/wiki\/Heapsort\">Heapsort on Wikipedia<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"<p>In the previous article, we introduced the heapsort algorithm and coded several helper functions in Python. In this article, we will finally code the heapsort function and test it on some input data. To recap, we already introduced the following functions: heapify: Turns a list into a binary heap. rebuildHeap: Accepts as input a heap [&hellip;]<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[3],"tags":[33,32,4],"class_list":["post-55","post","type-post","status-publish","format-standard","hentry","category-tutorials","tag-binary-heap","tag-heapsort","tag-python","entry"],"_links":{"self":[{"href":"http:\/\/pfsensesetup.com\/pythonscript.net\/wp-json\/wp\/v2\/posts\/55","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/pfsensesetup.com\/pythonscript.net\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/pfsensesetup.com\/pythonscript.net\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/pfsensesetup.com\/pythonscript.net\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"http:\/\/pfsensesetup.com\/pythonscript.net\/wp-json\/wp\/v2\/comments?post=55"}],"version-history":[{"count":2,"href":"http:\/\/pfsensesetup.com\/pythonscript.net\/wp-json\/wp\/v2\/posts\/55\/revisions"}],"predecessor-version":[{"id":57,"href":"http:\/\/pfsensesetup.com\/pythonscript.net\/wp-json\/wp\/v2\/posts\/55\/revisions\/57"}],"wp:attachment":[{"href":"http:\/\/pfsensesetup.com\/pythonscript.net\/wp-json\/wp\/v2\/media?parent=55"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/pfsensesetup.com\/pythonscript.net\/wp-json\/wp\/v2\/categories?post=55"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/pfsensesetup.com\/pythonscript.net\/wp-json\/wp\/v2\/tags?post=55"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}