# Program for Heap sorting using Python

## Introduction

Heap sort is based on the comparison technique of elements (based on Binary heap structure). The task is to sort the given element using heap sort.

## Program

```def heapify(arr, length, i):
max_ele = i
x = 2 * i + 1
y = 2 * i + 2
if x < length and arr[i] < arr[x]:
max_ele = x
if y < length and arr[max_ele] < arr[y]:
max_ele = y
if max_ele != i:
arr[i], arr[max_ele] = arr[max_ele], arr[i]
heapify(arr, length, max_ele)

def sort(arr, length):
for i in range(length // 2 - 1, -1 , -1):
heapify(arr, length, i)
for i in range(length-1, 0, -1):
arr[i], arr = arr, arr[i]
heapify(arr, i, 0)

ip_arr = [87, 895, 21, 1, 3]
print("The sorted array is: ")
sort(ip_arr, len(ip_arr))
for i in range(len(ip_arr)):
print(ip_arr[i])
```

## Output ## Explanation

Steps for heap sort:

• Build the max heap from the given array elements.
• The element at the root level is the largest, pick the root element and place it at the end of the heap. Reduce the size of the heap by 1.
• Repeat step 2 until the size of heap becomes 1.

This site uses Akismet to reduce spam. Learn how your comment data is processed.