Program for Heap sorting using Python


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.


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)):


Program for Heap sorting using Python


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.

Leave a comment

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