  # Python Code for Time Plot Complexity Heap Sort

NumPy | Python Methods and Functions

We implement a heap sort here, call it on random lists of different sizes, measure the time it takes for different sizes, and generate a plot of input size versus time.

 ` # Python code for implementation and execution algorithm ` ` # Complexity of the plot Heap Sort ` ` # Ashok Kajal ` ` # This Python code is designed to implement the heap sorting algorithm ` ` # Timeline graphs Complexity in the list different sizes `   ` # ----------- ---------- Important note ------------------- ` ` # numpy, time and matplotlib.pyplot are needed to run this code ` ` import ` time ` from ` ` numpy.random ` ` import ` ` seed ` ` from ` ` numpy.random ` ` import ` ` randint ` ` import ` ` matplotlib.pyplot as plt `     ` # find the left child of node i ` ` def ` ` left (i): ` ` return ` ` 2 ` ` * ` ` i ` ` + ` ` 1 `   ` # find the correct child of the node i ` ` def ` ` right (i): ` ` return ` ` 2 ` ` * i + 2 ``   # calculate and return the size of the array def heapSize (A): return len (A) - 1     # This function takes an array and Heapyfies # in the I node def M axHeapify (A, i): # print ("on the heap", me) l = left (i) r = right (i)   # heapSize = len (A) # print (& quot; left & quot ;, l, & quot; Rightt & quot ;, r, & quot; Size & quot ;, heapSize) if l & lt; = heapSize (A) and A [l] & gt; A [i]: largest = l else : largest = i if r & lt; = heapSize (A) and A [r] & gt; A [largest]: largest = r if largest! = i: # print (& quot; Largest & quot;, largest) A [i], A [largest] = A [ largest], A [i] # print (“List”, A) MaxHeapify (A, largest)   # this function creates a heapified array def BuildMaxHeap (A): for i in range ( int (heapSize (A) / 2 ) - 1 , - 1 , - 1 ): MaxHeapify (A, i)   # Sorting is done using the array heap def HeapSort (A):   BuildMaxHeap (A) B = list () heapSize1 = heapSize (A) for i in range (heapSize (A), 0 , - 1 ):   A [ 0 ], A [i] = A [i], A [ 0 ]    B.append (A [heapSize1]) A = A [: - 1 ]   heapSize1 = heapSize1 - 1 MaxHeapify (A , 0 )      # randomly generates a list of different # heapSort size and function call elements = l ist () times = list () for i in range ( 1 , 10 ):   # generate multiple integers   a = randint ( 0 , 1000 * i, 1000 * i) # print (s)   start = time.clock () HeapSort (a) end = time.clock ()   # print ("The sorted list is" and) print ( len (a), "Elements Sorted by HeapSort in " , end - start)   elements.append ( len (a)) times.append (end - start)   plt.xlabel ( ` List Length` ) plt.ylabel ( `Time Complexity` ) plt.plot (elements, times, label = `Heap Sort` ) plt.grid () plt.legend () plt.show () # This code is provided by Ashok Kajal `

Output:

` Input: Unsorted Lists of Different sizes are Generated Randomly Output: 1000 Elements Sorted by HeapSort in 0.023797415087301488 2000 Elements Sorted by HeapSort in 0.053856713614550245 3000 Elements Sorted by HeapSort in 0.08474737185133563 4000 Elements Sorted by HeapSort in 0.18377866 0.1658182863213824 6000 Elements Sorted by HeapSort in 0.1875901601906662 7000 Elements Sorted by HeapSort in 0.21982946862249264 8000 Elements Sorted by HeapSort in 0.2724293921580738 9000 Elements Sorted by HeapSort in 0.30996 Complexity PLot. python.engineering/wp-content/uploads/Heap-Sort-300x202.png "alt =" "width =" 300 "height =" 202 "class ="alignnone size-medium wp-image-567725 amp-wp-enforced- sizes "layout =" intrinsic ">  `