heapsort.py

# copyrights machine @Muzafar

# Heapsort with 4 children's

def heapsort(a, n):
    m = n
    m = m - 1
    buildHeap(a, m)
    print("This is min heap generated by build heap:\n", a)
    while m >= 1:
        a[0], a[m] = a[m], a[0]

        m = m - 1
        heapify(a, m, 0)


def heapify(a, m, i):
    min = i

    c1 = 4 * (i) + 1  # 4(i)+1,  1st  child of current node
    c2 = 4 * (i) + 2  # 4(i)+2,  2nd  child of current node
    c3 = 4 * (i) + 3  # 4(i)+3,  3rd  child of current node
    c4 = 4 * (i) + 4  # 4(i)+4, 4th  child of current node

    if c1 <= m and a[c1] < a[min]:  # 1st <  parent, 23 < 55
        min = c1
    if c2 <= m and a[c2] < a[min]:  # 2ND <  parent
        min = c2
    if c3 <= m and a[c3] < a[min]:  # 3RD <  parent
        min = c3
    if c4 <= m and a[c4] < a[min]:  # 4TH <  parent
        min = c4

    if min != i:  # run if any of children is smaller

        a[i], a[min] = a[min], a[i]
        # Recursively heapify the affected sub-tree
        heapify(a, m, min)


def buildHeap(a, n):
    # Index of last non-leaf node
    # heap build from bottom to top
    m = n // 4
    for i in range(m, -1, -1):
        heapify(a, n, i)


arr = [13, 12, 19, 58, 77, 55, 23, 99, 2, 37, 22, 66, 57,11, 36, 33, 99]
print('original array:\n', arr)
n = len(arr)
heapsort(arr, n)
print('sorted array :\n', arr)