The Min-priority Queue is an abstract data type (ADT) for maintaining a collection of elements, each with an associated value called a key. The ADT supports the following operations: • INSERT(Q,x): insert the element x into the queue Q. • MIN(Q): returns the element of Q with the smallest key. • EXTRACT-MIN (Q): removes and returns the element of Q with the smallest key. Implement in Java the Min-priority Queue ADT defined above using a) an array based binary heap b) a binary search tree. Observe that the ADT implementation operations should be in the form q.insert(x), q.min(), etc. Explain in the report your implementation, noting the running time (using bigOh notation) of each operation in both implementations. c) What are the worst-case running times of the three ADT operations when the underlying BST is self-balancing? Briefly explain your answer. d) Implement an extension of BST that allows MIN and EXTRACT-MIN operations in O(1). Briefly describe your imp
The Min-priority Queue is an abstract data type (ADT) for maintaining a collection of elements,
each with an associated value called a key. The ADT supports the following operations:
• INSERT(Q,x): insert the element x into the queue Q.
• MIN(Q): returns the element of Q with the smallest key.
• EXTRACT-MIN (Q): removes and returns the element of Q with the smallest key.
Implement in Java the Min-priority Queue ADT defined above using
a) an array based binary heap
b) a binary search tree.
Observe that the ADT implementation operations should be in the form q.insert(x),
q.min(), etc. Explain in the report your implementation, noting the running time (using bigOh notation) of each operation in both implementations.
c) What are the worst-case running times of the three ADT operations when the
underlying BST is self-balancing? Briefly explain your answer.
d) Implement an extension of BST that allows MIN and EXTRACT-MIN operations in O(1). Briefly describe your implementation in the report. Hint: maintain an extra pointer attribute in each node.
Step by step
Solved in 2 steps
