Heap Sort is a sorting algorithm based on the heap data structure. A heap is a tree based data structure where the tree is a complete binary tree. A complete binary tree is a binary tree in which all levels are completely filled, except the last level which may or may not be completely filled. Heaps can be of two types:

• Max Heap: In max heap, every parent node must have value greater than or equal to it's child's value.
• Min Heap: In min heap, every parent node must have value less than it's child's value.

We are going to use the Max Heap for heap sort here. The sorting process includes: construction of a heap from the data, a max heap precisely, swapping of the first and last node, removing the last node from the heap and processing it for the remaining. With each cycle, the heap gets smaller and the list gets to sort.

Illustration:

Algorithm

1. Construct max heap from the list
2. Swap the first node with the last node
3. Remove last node from heap
4. Perform step 1 to 3 for the remaining heap
5. Stop when heap empty

heapSort(list)
    n=length of list       
    for i from n//2-1 to -1 with inverval of -1 
        heapify(list,n,i)
    for i from n-1 to 0 with interval -1
        Swap valueAtIndex_i with valueAtIndex_0
        heapify(list,i,0)
heapify(list,lengthofdata,i)
    largest=i
    leftchildIdx,l=2*i+1
    rightchildIdx,r=2*i+2   
    if l<lengthofdata and valueAtlargest < valueAtl:
        largest=l
    if r<lengthofdata and valueAtlargest < valueAtr
        largest=r
    if largest!=i:
        swap valueAti with valueAtlargest
        perform recursion(heapify root), heapify(list,lengthofdata,largest)

Time Complexity:

• Worst Case: O(nlogn)
• Average Case: O(nlogn)
• Best Case: O(nlogn)

Space Complexity: O(1)

Program for Heap Sort:

def heapify(data, n, i):
    largest = i  
    l = 2 * i + 1     
    r = 2 * i + 2     
    # Check if left child of root exists and is greater than root
    if l < n and data[largest] < data[l]:
        largest = l
    # Check if right child of root exists and is greater than root
    if r < n and data[largest] < data[r]:
        largest = r
    # If needed, Change the root
    if largest != i:
        data[i], data[largest] = data[largest], data[i]  #Swap
        heapify(data, n, largest)   # Heapify Root.
def heapSort(data):
    n = len(data)
    # Building MaxHeap.
    for i in range(n//2 - 1, -1, -1):
        heapify(data, n, i)
    # Extract elements one by one
    for i in range(n-1, 0, -1):
        data[i], data[0] = data[0], data[i]  #Swap
        heapify(data, i, 0)
inp=input("Enter the data: ").split()
data=[]
for i in inp:
    data.append(int(i))
heapSort(data)
n = len(data)
print("Sorted List is")
print(data)

Output