Python Program for Heap Sort

Problem Statement:

Given an array, we have to sort it using heap sort.

Heap Sort is a sorting algorithm based on the binary heap data structure in which first we have to find the maximum element from the array, and then it will be replaced by the end element. Then, we will perform heapify on our heap, for maintaining the heap property. We will follow these steps until the array becomes sorted.

What is “Heapify”?

The process of changing a binary tree into a heap tree is known as heapify.

Algorithm:

  1. From the given array, build Max – Heap using heapify.
  2. The largest element is at the top of the Max – Heap will be swapped by the last element of the heap.
  3. Again perform heapify on the heap, to maintain the property of Heap Data Structure.
  4. Perform steps 2 and 3, till the size of the heap is greater than 1.

Now let’s watch the working of the Heap Sort Algorithm:

Code Implementation

def heapify(arr, n, i):
   
	largest = i
	l = 2 * i + 1 
	r = 2 * i + 2 

	if l < n and arr[i] < arr[l]:
	
		largest = l
	
	if r < n and arr[largest] < arr[r]:
	
		largest = r
	
	if largest != i:

		arr[i], arr[largest] = arr[largest], arr[i]
		heapify(arr, n, largest)

def heapSort(arr):
	
	n = len(arr)
	
	for i in range(n, -1, -1):
	
		heapify(arr, n, i)
	
	for i in range(n-1, 0, -1):
	
		arr[i], arr[0] = arr[0], arr[i]
		heapify(arr, i, 0)

arr = [71, 79, 9, 11, 14, 76, 54, 32]

heapSort(arr)
n = len(arr)

print ("After applying Heap Sort, the Array is:")

for i in range(n):
   print (arr[i],end=" ")

Output:
After applying Heap Sort, the Array is:
9 11 14 32 54 71 76 79

This article tried to discuss the Implementation Of Heap Sort in Python. Hope this blog helps you understand the concept. To practice problems on Heap you can check out MYCODE | Competitive Programming – Heaps.

Leave a Reply

Your email address will not be published. Required fields are marked *