DEV Community

loading...

Day 47 Of 100DaysOfCode: More About Algorithm(Heap Sort)

iamdurga profile image Durga Pokharel ・2 min read

Today is my 47th day of #100DaysOfCode and #python. Also continue to learned more about algorithm. Time and space complexity of heap sort. To understand about this sorting algorithm I took help of link.

Python Code

Heap is a specialize tree- based data structure. For a given node C, if P is a parent node of C then the value of P is greater than or equal to the value of C. The node at the top of the heap is called the root node.

def heapify(A, n, i):
    largest = i
    l = 2 * i + 1
    r = 2* i + 2
    if l < n and A[i] < A[l]:
        largest = l

    if r < n and A[largest] < A[r]:
        largest = r
    if largest != i:
        A[i],A[largest] = A[largest],A[i]
        heapify(A,n,largest)
def heapSort(A):
    n = len(A)
    for i in range(n//2 -1,-1,-1):
        heapify(A,n,i)
    for i in range(n-1,0,-1):
        A[i],A[0]= A[0],A[i]
        heapify(A,i,0)

A = [4,2,1,3,5,6]
heapSort(A)
n = len(A)
print('Sorted array is:')
for i in range(n):
    print('%d'%A[i]),
Enter fullscreen mode Exit fullscreen mode

Out put of the above code is,

Sorted array is:
1
2
3
4
5
6
Enter fullscreen mode Exit fullscreen mode

Discussion (0)

pic
Editor guide