USING PYTHON

Heap Performance Experiment

In this assignment, you will be conducting a simple experiment to show that removing minimum operations, in average, take time proportional to the binary logarithm of the input size. In doing so, you will

Create a HeapPriorityQueue class by making use of Code Fragments 9.1, 9.4, and 9.5 from the textbook,

Develop a function called test_heap that takes a single argument, n, which is the number of (key, value) pairs to be inserted to an instance of HeapPriorityQueue class, and then perform remove minimum operation on the heap object with each of the n items, and return the average and worst remove minimum times, and

Develop a report_results function that creates and saves a line chart where x-axis is n and the y-axis is the average and worst remove minimum times.

1.1 The test_heap Function

The test_heap function should work as follows. Initially, it should create an instance of HeapPriorityQueue class (Lets call it _heap). And then n distinct random integer numbers should be drawn from the range [0, 103n], and inserted to _heap object with the add operation (you can add the same number as key and value). At this moment, your heap should have n distinct numbers.

After filling the heap, you should perform remove minimum (remove_min) operation until the heap is empty. You will need to measure the time elapsed between the beginning and the end of the remove_min operation. And those elapsed time values should be saved in a temporary list called measures. Elapsed times for each remove_min operations can take time in the magnitude of nanoseconds. So you may want to save the time value in nanoseconds unit rather than seconds for the sake of simplicity.

Finally, test_heap function should return the average and maximum of values in measures as a tuple.

1.2 The report_results Function

report_results is a function that does not take a parameter, however, reports the results of a series of tests that you will perform with test_heap. The test_heap function will be called iteratively for the range of range (10000:1000001:10000) (i.e., there will be 100 iterations). After each iteration, a tuple with the following values will be appended to a list object: (n, avg_time, max_time). Lets call that list object results_list.

After having the results from this simple experiment, you will plot these results as a line chart by making use of the library module matplotlib. You are expected to learn how you can plot with plot function of matplotlib (https://matplotlib.org/stable/api/_as_gen/matplotlib.pyplot.plot.html).

plot function accepts one-dimensional number arrays as parameters. You can convert the results_list to a pandas data frame and then work with value vectors as follows.

1 # import pandas to use pandas DataFrame

2 import pandas as pd

3 # create DataFrame using data

4 df = pd . DataFrame ( results_list , columns =[ n, avg , max ])

5

6 # Then you can use df[ n ] , df[ avg ] , and df[ max ] as value vectors .

7 # matplotlib s plot function accepts value vectors , as you will find out.

The outcome of the execution of report_results function should be a single PDF file having a single line chart having two lines for average and maximum values plotted against n.

PLEASE USING PYTHON. THANK YOU!