Python Program for Heap Sort

Last Updated on December 14, 2022 by Prepbytes

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.

Other Python Programs
Python program to reverse a number
Python Program to Add Two Numbers
Python program to check armstrong number
Python program to check leap year
Python program to convert celsius to fahrenheit
Python program to find factorial of a number
Python program to find the middle of a linked list using only one traversal
Python program to reverse a linked list