Python Heap Sort Program - Complete Guide with Examples

Heap Sort

In this tutorial, we will learn how to write a program for Heap Sort algorithm.

Program

In the following program, we write a function heap_sort() that takes a list of numbers, and sorts them in ascending order.

We also show how to use list.reverse() method, to reverse the order of a default sorted list, to get descending order.

Python Program

def heap_sort(alist):
    build_max_heap(alist)
    for i in range(len(alist) - 1, 0, -1):
        alist[0], alist[i] = alist[i], alist[0]
        max_heapify(alist, index=0, size=i)
 
def parent(i):
    return (i - 1)//2
 
def left(i):
    return 2*i + 1
 
def right(i):
    return 2*i + 2
 
def build_max_heap(alist):
    length = len(alist)
    start = parent(length - 1)
    while start >= 0:
        max_heapify(alist, index=start, size=length)
        start = start - 1
 
def max_heapify(alist, index, size):
    l = left(index)
    r = right(index)
    if (l < size and alist[l] > alist[index]):
        largest = l
    else:
        largest = index
    if (r < size and alist[r] > alist[largest]):
        largest = r
    if (largest != index):
        alist[largest], alist[index] = alist[index], alist[largest]
        max_heapify(alist, largest, size)

			
nlist = input('Enter the list of numbers separated by space\n').split()
nlist = [int(x) for x in nlist]
heap_sort(nlist)
print('Sorted List after Heap Sort, in Ascending Order\n', nlist)
nlist.reverse()
print('Sorted List after Heap Sort, in Descending Order\n', nlist)

Output

Enter the list of numbers separated by space
1 74 96 5 42 63
Sorted List after Heap Sort, in Ascending Order
 [1, 5, 42, 63, 74, 96]
Sorted List after Heap Sort, in Descending Order
 [96, 74, 63, 42, 5, 1]