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

Sentry image

See why 4M developers consider Sentry, “not bad.”

Fixing code doesn’t have to be the worst part of your day. Learn how Sentry can help.

Learn more

Top comments (0)

Image of Timescale

🚀 pgai Vectorizer: SQLAlchemy and LiteLLM Make Vector Search Simple

We built pgai Vectorizer to simplify embedding management for AI applications—without needing a separate database or complex infrastructure. Since launch, developers have created over 3,000 vectorizers on Timescale Cloud, with many more self-hosted.

Read more