DEV Community

Durga Pokharel
Durga Pokharel

Posted on

3

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

Heroku

Build apps, not infrastructure.

Dealing with servers, hardware, and infrastructure can take up your valuable time. Discover the benefits of Heroku, the PaaS of choice for developers since 2007.

Visit Site

Top comments (0)