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) .
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.
