DEV Community

Durga Pokharel
Durga Pokharel

Posted on

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

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

Day 47 Of #100days Of Code and #Python
* More about Algorithm
* Heap Sort
* Best Case Time Complexity O(nlogn)
* Worst Case time Complexity O(nlogn)
* Space Time complexity O(1)#womenintech #100DaysOfCode #DEVCommunity #CodeNewbie pic.twitter.com/cHqq6Vmpw3

— Durga Pokharel (@mathdurga) February 9, 2021

Top comments (0)