Implement the class Heap and the class BST, each containing an Insert() and DeleteHighest() operations.
computer science
Description
In this assignment, we will compare the BSTs and Heaps operations in two respects:
a) INSERT and DELETEHIGHEST
b) Sorting
A) We've seen in class how the two Priority Queue operations "insert" and “deleteHighest" can be implemented with a
heap, in O(n log n) . In this assignment, you are asked to implement the same two operations also on a BST (we’ve also
seen in class how to insert in a BST). You should then compare the behaviour of the two ADTs for these two operations.
Here are the steps:
1. Implement the class Heap and the class BST, each containing an Insert() and DeleteHighest() operations.
2. Generate a random sequence (of size n) of numbers. Store the sequence in a List (you will also need to implement a List class).
3. Insert the n numbers generated in the Heap structure.
4. Insert the same random numbers in a BST.
5. Iteratively apply deleteHighest on both the Heap and the Tree, storing the deleted elements in two different Lists.
6. Compares the two Lists to make sure the sequence of DeleteHighest was the same
B) We now need to compare how the two ADTs can sort elements
7. Re-insert the random numbers generated in step 2 above back in the Heap and in the Tree.
8. Apply heapSort on the heap then copy the heapArray in a List.
9. Apply Inorder traversal on the Tree and store the resulting sequence in a List.
10. Compare the two Lists to make sure the sequence of sorted elements was the same.
