In Part-1 of the heap sort algorithm, we have discussed how we can represent a tree in array format, what is a heap, types of the heap (max-heap & min-heap), and then how to insert an element in max-heap. Now, In this section, we will see the Heap Sort Algorithm in Python and how it works with an example, then we will discuss the time complexity and space complexity. Afterward, In the end, we will compare heap sort with merge sort and quick sort. If you have not studied Part-1 topics it will be difficult for you to understand the heap sort. That’s why it is not suggested to skip those topics.
What you’ll learn?
- Working of Heap Sort with example
- Heap sort algorithm for sorting an array in ascending order
- Implementation of heap sort in python
- Time complexity
- Space complexity
- Does heap sort an in-place algorithm?
- How commonly we use heap sort?
- Features
- Comparison between heap sort quicksort and merge sort
Working of Heap Sort with example
In Heap Sort, the given input array is first converted to a Complete Binary Tree. Then, a Heapify() function is called that changes the Complete Binary Tree to a Max Heap. It is being done so that the largest element from the array can be obtained easily.
Now, once a Max Heap is created, then a swap operation between the Node and the element at the lowest level of the heap is performed. After swapping, we get the largest element of the array at the lowest level of the heap, and then a deletion operation is performed. In this deletion operation, the node being at the lowest level i.e., the largest element of the array is removed.
The element being removed is inserted in a Queue. Since we know that in Heap Sort, we also require a Queue data structure. The use of this queue is to hold the removed elements pop then back in the form of a sorted array.
After deletion, the resultant elements will again undergo Heapify() function and all the above mentioned steps will be performed again.
Let us understand with an example
Input : 70 27 12 8 68 96 34
Output : 8 12 27 34 68 70 96
Create a Complete Binary Tree for the given array and then convert that complete binary tree to a max-heap by using the function heapify()
Now what we will do, we will swap the root node (96) with the last node that is 34 and after swapping we will remove the element 96.
Now as you can see it’s not a max-heap as it is violating the condition so again we will perform the Heapify() function to change this to a max-heap. And then follow the same procedure as we did earlier. We will swap the root node with the last node then after swapping we will remove that last and check if it’s a max heap or not.
Resultant Queue –
From the Queue, shown above, elements will pop one-by-one, giving us the sorted sequence of array elements (in ascending order), which is the desired output.
This is how, Heap Sort works.
Algorithm of Heap sort
Step1: Create a max-heap from the given array.
Step2: In a max-heap, largest item is stored at the root of the heap.
Replace it with the last item of the heap and reduce the size of heap by 1.
Finally, call heapify() to heapify the root of the tree.
Step3: Go to Step 2 while size of heap is more than 1.Python Code
# CODE BY COPYASSIGNMENT
# heapify tree rooted at index i
def heapify(arr, n, i):
largest = i # In max-heap largest is at root
l = 2 * i + 1 # left child index = 2*i + 1
r = 2 * i + 2 # right child index = 2*i + 2
# See if left child of root exists and > root
if l < n and arr[i] < arr[l]:
largest = l
# See if right child of root exists and > root
if r < n and arr[largest] < arr[r]:
largest = r
# update root if required
if largest != i:
arr[i],arr[largest] = arr[largest],arr[i] # swap
# Heapify the root
heapify(arr, n, largest)
# heap sort definition
def heapSort(arr):
n = len(arr)
for i in range(n // 2 - 1, -1, -1):
heapify(arr, n, i)
# extracting elements
for i in range(n-1, 0, -1):
arr[i], arr[0] = arr[0], arr[i] # swap
heapify(arr, i, 0)
arr = [ 12, 11, 13, 5, 6, 7]
heapSort(arr)
n = len(arr)
print ("Sorted array is")
for i in range(n):
print ("%d" %arr[i])Output:
Time Complexity of Heap Sort
As we have discussed in the previous section, the heap sort algorithm uses two different functions. First is the Heapify() function. Initially, we have used Heapify() to build a max-heap out of the complete binary tree. After that, we have used it after every delete operation, so that we can get the largest element. Now, the time Complexity for Heapify() function is O(log n) because, in this function, the number of swappings done is equal to the height of the tree.
The second function which heap sort algorithm used is the BuildHeap() function to create a Heap data structure. Time Complexity of BuidlHeap() function is O(n). Thus, the combined time complexity for the heap sort algorithm becomes O(n log n) for all three cases. Thus the time complexity of heap sort for the best case, average case, and worst-case O(nlogn).
Space Complexity of Heap Sort
For an algorithm, space complexity is defined as the memory space occupied by it to run and execute all its operations. For Heap Sort Algorithm, Space Complexity is O(1) because it involves constant swapping of elements for which the space required is equivalent to only one element.
Is heap sort an in-place algorithm?
Yes, Heap Sort is an in-place sorting algorithm because it does not require any other array or data structure to perform its operations. We do all the swapping and deletion operations within one single heap data structure.
How commonly we use heap sort?
We don’t use heap sort so often. As the programming of heap sort is a little bit complex so we don’t prefer it. In case, we have a choice we generally prefer Merge Sort and Quicksort. But remember if we already have a heap data structure in our program then we will go for heap sort.
Features
- As we have learned, in heap sort we create a max heap, through which we can find the maximum element of the array. In a similar way, we can also create a min-heap by modifying the algorithm a little bit. This can be very handy when we need to perform some arbitrary searches.
- In the case of the worst-case data set, heap sort serves a better purpose than quicksort because of its time complexity as discussed earlier.
- It is an in-place algorithm.
- When we have a heap data structure in our program, then we prefer heap sort in this scenario.
Comparison between heap sort quicksort and merge sort
Quicksort, Merge sort and Heap sort perform very differently when we take different and large data sets because if we take small data sets then the execution will be very fast and no marginal difference will be observed. If the data sets are large in size, then it will affect the memory space and size and we will be able to easily differentiate which one is better among the three.
However, the above-mentioned sorting algorithms have a common time complexity i.e., O(n log n). But Quicksort has a time complexity of O(n2) in the worst-case whereas both Heap sort and Merge sort have a time complexity of O(n log n) even in the worst case.
Quicksort and Merge sort both work on a recursive algorithm or you can say they use recursion, on the other hand, there is no such recursive algorithm in Heap sort. In Quicksort, since we select a pivot element randomly, thus, it sometimes serves as the fastest sorting algorithm if we choose a favorable data set. Whereas in the case of linked lists, the merge sort serves the best.
Check this video for more:
Credits to nETSETOS
Thanks for reading!
If you found this article useful please support us by commenting “nice article” and don’t forget to share it with your friends and enemies! If you have any query feel free to ask in the comment section.
Happy Coding!
You may also read
Introduction to Searching Algorithms: Linear Search Algorithm
Bubble Sort Algorithm In Data Structures & Algorithms using Python
Merge Sort Algorithm in Python
Sorting Algorithms and Searching Algorithms in Python
Shutdown Computer with Voice in Python
