{"id":453,"date":"2023-05-04T20:00:22","date_gmt":"2023-05-04T20:00:22","guid":{"rendered":"https:\/\/vmlogger.com\/algorithms\/?p=453"},"modified":"2023-05-04T20:01:30","modified_gmt":"2023-05-04T20:01:30","slug":"heap-sort-an-explanation-and-implementation","status":"publish","type":"post","link":"https:\/\/vmlogger.com\/algorithms\/2023\/05\/04\/heap-sort-an-explanation-and-implementation\/","title":{"rendered":"Heap Sort : An Explanation and Implementation"},"content":{"rendered":"
In the series of sorting algorithms<\/a>, this is the 4th sorting algorithm which is quite popular because of its better time complexity. From the name of this sorting algorithm, you can already guess that this sorting method is based on the Heap data structure<\/a>. It was first proposed by J.W.J. Williams in 1964 and was later improved by R.W. Floyd in 1969. We have already learned about Heap data structure<\/a> implementation in Python. In this article, we will discuss the Heap Sort algorithm and its implementation in Python.<\/p>\n The heap Sort algorithm works by building a binary heap from the input array and then repeatedly extracting the maximum or minimum element from the heap and placing it at the end of the sorted array. The process is repeated until all the elements are sorted.<\/p>\n The heap Sort algorithm has a time complexity of The Heap Sort algorithm works as follows:<\/p>\n In this phase, a binary heap is built from the input array. A binary heap is a complete binary tree where the parent node is always greater than its child nodes. There are two types of binary heaps: max heap and min heap. In the Heap Sort algorithm, we use a max heap, where the root node is the maximum element in the heap. In this phase, we repeatedly extract the maximum element from the heap and place it at the end of the sorted array. After each extraction, we heapify the remaining elements to maintain the heap property. We repeat this process until all the elements are sorted. It is done by the following piece of code:<\/p>\n The heap Sort algorithm is a popular and efficient sorting algorithm that uses a binary heap data structure to sort elements. It has a time complexity of In the series of sorting algorithms, this is the 4th sorting algorithm which is quite popular because of its better time complexity. From the name of this sorting algorithm, you can already guess that this sorting method is based on the Heap data structure. It was first proposed by J.W.J. Williams in 1964 and was […]<\/p>\n","protected":false},"author":45,"featured_media":467,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_et_pb_use_builder":"","_et_pb_old_content":"","_et_gb_content_width":"","footnotes":""},"categories":[4,10],"tags":[],"class_list":["post-453","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-difficult","category-sorting"],"yoast_head":"\nHeap Sort Algorithm<\/h2>\n
O(n log n)<\/code>, which makes it one of the fastest sorting algorithms. It is also an in-place sorting algorithm, meaning it does not require additional memory to sort the array.<\/p>\n
How does Heap Sort Algorithm work?<\/h2>\n
\n
Step 1. Building a Heap data structure<\/a>:<\/h3>\n
\nTo build a heap from an array, we start from the middle element of the array and heapify each sub-tree until the entire array is heapified. The heapify operation is performed by comparing the parent node with its child nodes and swapping them if necessary.<\/p>\n\r\n# to build the heap at first\r\ndef buildHeap(array):\r\n parentNodeIdx = (len(array) - 2) \/\/ 2\r\n for idx in reversed(range(parentNodeIdx + 1)):\r\n moveDown(array, idx, len(array) - 1)\r\n\r\ndef moveDown(heap, startIdx, endIdx):\r\n childOneIdx = startIdx * 2 + 1\r\n while childOneIdx <= endIdx:\r\n if (startIdx * 2 + 2) <= endIdx:\r\n childTwoIdx = startIdx * 2 + 2\r\n else:\r\n childTwoIdx = -1\r\n if childTwoIdx != -1 and heap[childTwoIdx] < heap[childOneIdx]:\r\n possibleSwapIdx = childTwoIdx\r\n else:\r\n possibleSwapIdx = childOneIdx\r\n if heap[possibleSwapIdx] < heap[startIdx]:\r\n heap[startIdx], heap[possibleSwapIdx] = (\r\n heap[possibleSwapIdx],\r\n heap[startIdx],\r\n )\r\n startIdx = possibleSwapIdx\r\n childOneIdx = startIdx * 2 + 1\r\n else:\r\n return\r\n<\/pre>\n
Step 2,3 and 4: Extracting Maximum Element and repeat the same process<\/h3>\n
\r\ndef heapSorting(array):\r\n\r\n \"\"\"\r\n Complexity:\r\n best : O(n log(n))\r\n average : O(n log(n))\r\n worst : O(n log(n))\r\n parameters:\r\n arrayToSort : Array to be sorted\r\n\r\n returns:\r\n sorted array\r\n \"\"\"\r\n\r\n buildHeap(array)\r\n for idx in reversed(range(1, len(array))):\r\n array[0], array[idx] = array[idx], array[0]\r\n moveDown(array, 0, idx - 1)\r\n return array\r\n<\/pre>\n
Conclusion<\/h2>\n
O(n log(n))<\/code> in all cases such as worst, average, and best. Keep in mind that it is an in-place sorting algorithm, which means you do not need to define any other array or data structure to store the sorted array rather sorting happens in the same array space. In this article, I have discussed the Heap Sort algorithm and its implementation in Python. Do let me know your thoughts on this algorithm in the comments below. If you like it share it with your friends and colleagues.<\/p>\n<\/span>","protected":false},"excerpt":{"rendered":"