From our earlier posts, we are aware of what a heap is and how basic operations are performed on a heap. One of the basic operations is deletion. Have we ever given a thought to utilizing the deletion operation to execute some other operation? To be honest, even I didn’t know it for some time. You might also not know while you are reading this post. I don’t want to waste your time anymore, let’s dive into details.
Note: Go through the deletion operation on a max heap for better understanding.
Heap Sort:
When we delete an element from the array, an empty space is left in the array, which is no longer part of the heap. We will utilize this space to sort the elements of the array.
Some key points:
- The root of the max-heap is always the highest element. If not we have to arrange the elements to make it a max heap.
- The parent node can be found using [floor(n/2)-1] in an array.
- The left child of the parent is (2*position of the parent in the array(say i)+1) and the right child is ((2*i)+2)). The variation in the formula is because we are implementing it here in a programming language.
- Heapify is used to form the max heap.
Assuming that the tree satisfies the property of max heap, we will now look into the working of heapsort.
Working of Heapsort:
Swapping: Since the largest element is the root i.e. at the first position of the array, swap it with the last element of the array.
Remove: Decrease the size of the heap by 1 which decreases the size of the array.
Heapify: Heapify the root element so that we will have the highest element at the root.
Repeat this process until all the elements are sorted. The below picture depicts how an element is removed and heapify is performed.
The below image shows the procedure of heap sort without larger steps but concluding them at once.
IMPLEMENTATION IN PYTHON
def heapify(arr,n,i): #to form max heap
highest=i
left=(2*i)+1 #left node of the parent
right=left+1 #right node of the parent
#extracting the largest of the three
#i.e. parent and its children
if left<n and arr[i]<arr[left]:
highest=left
if right<n and arr[highest]<arr[right]:
highest=right
#if the chosen parent is not the highest
#swap it with the largest
if highest!=i:
#swapping the largest
arr[i],arr[highest]=arr[highest],arr[i]
heapify(arr,n,highest)
def heapSort(arr):
n=len(arr)
#n//2 gives the first parent node
#every node after n//2 is a leaf node.
for i in range(n//2,-1,-1):
heapify(arr,n,i)
#heapifying after deletion operation
for i in range(n-1,0,-1):
#swapping the last element with the root
arr[0],arr[i]=arr[i],arr[0]
heapify(arr,i,0)
arr = [60,50,45,40,35,20,25,30]
heapSort(arr)
n = len(arr)
print("Sorted array is: ")
for i in range(n):
print("%d " % arr[i], end='')# your code goes here
Click Here to download the code.
Time Complexity:
The processes involved are creating the heap and deleting them to sort. The time taken to create the heap is n log n and the time taken for deletion is also n log n. The total time hence taken for sorting the elements in an array using heap is O(2n log n) which is O(n log n).
Techprodezza 