CS304 Assignment 5 - Comparing BST with Heap

Due Sunday April 4th at 11:59 PM

In this assignment, you will compare the performance of binary search trees (BST) with the heap. In particular, we are interested in verifying the time complexity of the following operations:

insert(elem)

deleteMin()

sort(array)

step 1: implement the BST in C++. You may use the code provided in lecture 14, or create your own.

● I have provided a working version of the lecture 14 BST code on moodle (BinarySearchTree.h)

step 2: implement the max heap in C++. You may use the code provided in lecture 15, or create your own.

● I have provided a working version of the lecture 15 heap code on moodle. (BinaryHeap.h)

● The max heap is the type of heap where the top element is always the largest element in the heap

If you use my implementations, be sure to study this code and review the notes from lectures 14, 15! I may ask questions on it during the final interview.

step 3: create a vector of 100,000 random integers in your main. You can do this by filling a vector up with 100,000 ints from 0-99,999 and then permuting the vector (this ensures no duplicates are created, which is important because my BST does not handle duplicates well). I show how to create this vector in my main (provided on moodle).

step 4: perform the following:

● In a ‘for’ loop, insert all 100,000 elements into both heap and BST. Get the time of each ‘insert’ operation in nanoseconds. Write the results to a text file (this will produce two text files, each with 100,000 numbers).

● After both heap and BST are filled with elements (from the 100,000 inserts just performed), remove the elements one by one, using deleteMin() for the heap, and findMin() followed by remove(elem) on the BST. Time these operations to see how long it takes to remove the min from each data structure, save results to txt file.

● Modify both the heap and the BST classes to implement a function that performs heapsort (for the heap) and treesort (for the BST). The function should take as input a reference to a vector of unsorted elements and return the vector in sorted order. The function will be relatively simple, and rely on pre-existing heap/BST operations. Heapsort can be performed by simply building the heap and then calling deleteMin repeatedly until the heap is empty. Treesort can be performed by building the tree and then performing an inorder traversal to get the elements in sorted order. Both sorting algorithms are O(nlogn).

● Once you have created your sorting functions, time both data structures on random vectors of ints with n = 1000 − 100,000 in increments of 1000. So you will have 100 time values for each data structure. Save the times to a text file.

Step 5: visualize your results – using the visualization software of your choice (I have provided an example python script on moodle), create the following plots:

1) BST vs heap time in nanoseconds for insertions from 1-100,000 elements

2) BST vs heap time in nanoseconds for deleteMin from 100,000-1 elements

3) Treesort vs heapsort time in nanoseconds, for random vectors with n = 1000 − 100,000 elements (increments of 1000

On all plots, the x-axis is the number of elements currently in the data structure or the vector to be sorted, and the y-axis is the time in nanoseconds.

In a single zip file, submit your main (used for timing and writing the values to text file), your heap/BST source code, and a pdf containing the 3 plots (an example of plot 1 is on moodle).