Source: https://www.youtube.com/watch?v=40iljMQmqmY

Heap Sort

Complete Binary Tress:

height of a node in a tree: number of edges going via the longest route to the leaf nodes.

Height of the tree = height of the root node.

• Number of nodes in a complete Binary tree: $$2^{height+1}$$ - 1

Min Heap:

Time to insert in min heap : O(log(n))

Time to find min: O(1)

Time to delete min: O(log(n))

Heap is a binary tree or 3-ary tree or ... n-ary tree.

property of a binary tree: every node will have atmost 2 children.

Heap is an almost complete binary tree. and a complete binary tree.

tree is filled: left to right

Heap Sort:

Heap sort is a comparison based sorting technique based on Binary Heap data structure.

What is Binary Heap?

A Binary Heap is a Complete Binary Tree where items are stored in a special order such that value in a parent node is greater(or smaller) than the values in its two children nodes. The former is called as max heap and the latter is called min heap. The heap can be represented by binary tree or array.

Why array based representation for Binary Heap?

Since a Binary Heap is a Complete Binary Tree, it can be easily represented as array and array based representation is space efficient. If the parent node is stored at index I, the left child can be calculated by 2 * I + 1 and right child by 2 * I + 2 (assuming the indexing starts at 0).

To get parent index of a node: floor((node's index)/2)

Heap Sort Algorithm for sorting in increasing order:

1.Build a max heap from the input data.

2.At this point, the largest item is stored at the root of the heap. Replace it with the last item of the heap followed by reducing the size of heap by 1. Finally, heapify the root of tree.

3.Repeat above steps while size of heap is greater than 1.

def max_heapify(A,i):
    if i == 0:
        left_child = 1
        right_child = 2

    else:
        left_child = (2*i)+1
        right_child = left_child+1

    if left_child<len(A) and A[left_child]>A[i]:
        largest = left_child
    else:
        largest = i

    if right_child<len(A) and A[right_child]>A[largest]:
        largest = right_child

    if largest!=i:
        (A[largest],A[i]) = (A[i],A[largest])
        max_heapify(A,largest)
    #print(A)

def build_max_heap(A):
    for i in range(int((len(A)/2))-1,-1,-1): #We have taken len(A)/2-1 to 0 as index len(A)/2+1 onwards there are only leaf nodes and leaf nodes are already heaps so no need to max_heapify them
        max_heapify(A,i)
    return A

def extract_max(A): #Swaps the first element with the last. Now last element will be max so remove the last and return it. Thus it is returning the maximum value and decreasing the node by 1
    max = A[0]
    last = A.pop()
    A[0] = last
    max_heapify(A,0)
    return max

def heapSort(arr):
    n = len(arr)
    ans = []

    arr = build_max_heap(arr) #Will return a max heap i.e [8,4,7,1,3,5]

    while len(arr)>1: #You can't do 0 as it will give index out of bounds error as in the ExtractMax it wont be able to pop any element.
        ans.append(extract_max(arr)) 

    ans.append(arr[0]) #As we have done >1 in the previous loop, the arr still has one element which is the minimum one so we append it to our ans array
    return ans


a = [4,3,7,1,8,5]
ans = heapSort(a)
print(ans)

Time complexity of heap sort : O(n log(n)) --> heapify takes log(n) and its called n times.