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]),
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
Top comments (0)