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[0] = arr[0], 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.