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.
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= A,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]),
Out put of the above code is,
Sorted array is: 1 2 3 4 5 6
Day 47 Of #100days Of Code and #Python— Durga Pokharel (@mathdurga) February 9, 2021
* 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