Description
For this lab you will compare the performance of two heap structures—the binary heap and the min-max heap using the functions you wrote for previous labs.
You are to compare the structures on data sets of sizes n = 100,000, n= 200,000, and n = 400,000. Put the n integers into an array of size n + 1,000 (to allow for the possibility that inserts will make the heap size larger than n). Then, use buildheap to construct the original heap.
You will then do timing tests by performing a sequence of insert and deletemin operations. (This is described in more detail below.) Remember that exactly the same data must be used to test the two structures. (You may not store any values for later use with the other structure.) In your report you are to include the number of operations performed and the amount of time required for each data set, for each structure.
Run a total of 8 tests for each data set size for each structure. Be sure to run all tests for one value of n before beginning any tests for the next value of n. Specifically, perform the following steps for each test:
Starting with the binary heap,
- Using an array of size n + 1,000, generate n integers in the range from –n to n.
- Start the timer and use buildheap to construct the initial heap. Stop timing and record how long buildheap took.
- Generate a random number k between 1 and 50,000. k is the number of operations you are to perform.
- Start timing again and perform the following a total of k times:
Generate a random number x between 0 and 1.
- If x < 0.5 perform a deletemin operation
- Else, generate another random number y between –n and n and insert y into the heap.
- Stop timing and record both the number of operations performed (the k value) and the total amount of time required to perform those operations.
- Using the same array repeat steps 1 – 5 until a total of 8 tests have been run.
Then, using the same methodology repeat the process for the other values of n for the binary heap. After finishing the tests for the binary heap repeat this same process for the min-max heap.
Turn in a report that includes the code you wrote to structure the testing. Also, in table format report all the results of the timing tests. There should be a total of 48 tests—24 for each structure with eight tests for each value of n. For each test include the time required for buildheap, the number of operations performed and the time required to complete those operations. Finally, compare the two structures and any conclusions you can draw from the data. Be sure to justify your conclusion.
Due by Midnight Saturday.
