Program for Heap sorting using Python

by | Jun 17, 2021 | Python Programs

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

Program for Heap sorting using Python

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.

Author

0 Comments

Submit a Comment

Your email address will not be published. Required fields are marked *

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