Python code for Time complexity plot of Heap sort

By Richa Sirwani

In this tutorial, we will write the Python program for the time complexity plot of heap sort.

Heap:
A heap is a complete binary tree where the value of parent is greater than its child nodes (Max Heap) or is smaller than its child nodes (Min Heap).
The sorting algorithm that uses Heap to sort the elements is called heap sort. The formula 2*i is used to calculate the position of the left child and that of the right child, 2*i+1.

To visualize the time complexity of the heap sort, we will implement heap sort a list of random integers. Python matplotlib.pyplot is used to plot the graph and NumPy to generate random integers. time.process_time() gives the sum of user space CPU and the kernel time.

So below is our Python code for Time complexity plot of Heap sort

import time
import numpy as np
import matplotlib.pyplot as plt

def maxheap(a,i):
    l=2*i
    r=2*i +1
    n= len(a)-1
    if(l<=n and a[l]>a[i]):
        large=l
    else:
        large=i
    if(r<=n and a[r]>a[large]):
        large=r
    if(large!=i):
        temp=a[i]
        a[i]=a[large]
        a[large]=a[i]
        maxheap(a,large)
        
def build_heap(a): 
    leaf=int(len(a)/2)
    for i in range(leaf -1, -1, -1): 
        maxheap(a, i) 
def heapsort(a):
    build_heap(a)
    n= len(a)-1
    for i in range(int(n),0,-1):
        a[i],a[0]=a[i],a[0] #easy way to swap elements directly
        n=n-1
        maxheap(a,0)

dict1={}       #using dictionary to store the time taken by each set of elements
for i in range(1,10):
    a=np.random.randint(0,i*5000,i*1000)
    st=time.process_time()
    heapsort(a)
    end=time.process_time()
    dict1[len(a)]=(end-st)
    print("Time taken by " + str(len(a)) + " numbers is " + str(dict1[len(a)]))
print("Following graph depicts the Time Complexity plot for heap sort:")
plt.xlabel("Elements in a heap")
plt.ylabel("Time")
plt.title("Heap Sort Time Complexity")
plt.plot(*zip(*sorted(dict1.items())))
plt.show()

Output of the above program and Time Complexity Plot:

Time taken by 1000 numbers is 0.006170349999999658 
Time taken by 2000 numbers is 0.017003724000000275 
Time taken by 3000 numbers is 0.015554909999999644 
Time taken by 4000 numbers is 0.016545511000000346 
Time taken by 5000 numbers is 0.016028323000000455 
Time taken by 6000 numbers is 0.021886925000000446 
Time taken by 7000 numbers is 0.022509170999999384 
Time taken by 8000 numbers is 0.026082438999999624 
Time taken by 9000 numbers is 0.030361662999999872 
Following graph depicts the Time Complexity plot for heap sort:

Time Complexity of heap sort is O(n log(n)).
Applications of HeapSort:

1. k-sorted or nearly sorted array.

2. Find Largest Derangement of Sequence in Heap.

3. Encode a String in Huffman Coding.