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 later improved by R.W. Floyd in 1969. We have already learned about Heap data structure implementation in Python. In this article, we will discuss the Heap Sort algorithm and its implementation in Python.
Heap Sort Algorithm
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.
The heap Sort algorithm has a time complexity of O(n log n), 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.
How does Heap Sort Algorithm work?
The Heap Sort algorithm works as follows:
- First build a maxHeap data structure from the provided array
- The first item of the heapified array will the maximum among all the array items [based on the definition of maxHeap Data structure]
- Replace the last item with this first item. This way, the highest value becomes the last item in the array
- Now, repeat the same process on the same array by one less time than the previous one [because after every loop, the last item will be at the right place ]
Step 1. Building a Heap data structure:
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.
To 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.
# to build the heap at first
def buildHeap(array):
parentNodeIdx = (len(array) - 2) // 2
for idx in reversed(range(parentNodeIdx + 1)):
moveDown(array, idx, len(array) - 1)
def moveDown(heap, startIdx, endIdx):
childOneIdx = startIdx * 2 + 1
while childOneIdx <= endIdx:
if (startIdx * 2 + 2) <= endIdx:
childTwoIdx = startIdx * 2 + 2
else:
childTwoIdx = -1
if childTwoIdx != -1 and heap[childTwoIdx] < heap[childOneIdx]:
possibleSwapIdx = childTwoIdx
else:
possibleSwapIdx = childOneIdx
if heap[possibleSwapIdx] < heap[startIdx]:
heap[startIdx], heap[possibleSwapIdx] = (
heap[possibleSwapIdx],
heap[startIdx],
)
startIdx = possibleSwapIdx
childOneIdx = startIdx * 2 + 1
else:
return
Step 2,3 and 4: Extracting Maximum Element and repeat the same process
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:
def heapSorting(array):
"""
Complexity:
best : O(n log(n))
average : O(n log(n))
worst : O(n log(n))
parameters:
arrayToSort : Array to be sorted
returns:
sorted array
"""
buildHeap(array)
for idx in reversed(range(1, len(array))):
array[0], array[idx] = array[idx], array[0]
moveDown(array, 0, idx - 1)
return array
Conclusion
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 O(n log(n)) 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.
0 Comments