Get free ebooK with 50 must do coding Question for Product Based Companies solved
Fill the details & get ebook over email
Thank You!
We have sent the Ebook on 50 Must Do Coding Questions for Product Based Companies Solved over your email. All the best!

# 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.