Python Program to Implement Heap Sorting

01. Example:

def heapSorting(data):
    buildMaxHeap(data)
    for i in range(len(data) - 1, 0, -1):
        data[0], data[i] = data[i], data[0]
        maxHeapify(data, 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 buildMaxHeap(data):
    length = len(data)
    start = parent(length - 1)
    while start >= 0:
        maxHeapify(data, index=start, size=length)
        start = start - 1
 
def maxHeapify(data, index, size):
    l = left(index)
    r = right(index)
    if (l < size and data[l] > data[index]):
        largest = l
    else:
        largest = index
    if (r < size and data[r] > data[largest]):
        largest = r
    if (largest != index):
        data[largest], data[index] = data[index], data[largest]
        maxHeapify(data, largest, size)
 
 
list01 = input('Enter the list of numbers: ').split()
list01 = [int(x) for x in list01]

heapSorting(list01)

print('nSorted list: ', end='')
print(list01)

Output:

Enter the list of numbers: 320 420 140 500 185 60 200 80 10 100
Sorted list: [10, 60, 80, 100, 140, 185, 200, 320, 420, 500]

 

Leave a comment