Problem 3: Almost a priority queue. Design a data structure that supports the following operations for almost a priority queue: (i) FindSecondSmallest () which returns the second smallest item in the data structure. (ii) Insert(x) which inserts item x to the data structure. (iii) DeleteSecond Smallest() which removes the second smallest item from the data structure. Your data structure should implement the operation FindSecondSmallest () in O(1), and the other two operations in O(logn), where n is the number of elements in the data structure.
Problem 3: Almost a priority queue. Design a data structure that supports the following operations for almost a priority queue: (i) FindSecondSmallest () which returns the second smallest item in the data structure. (ii) Insert(x) which inserts item x to the data structure. (iii) DeleteSecond Smallest() which removes the second smallest item from the data structure. Your data structure should implement the operation FindSecondSmallest () in O(1), and the other two operations in O(logn), where n is the number of elements in the data structure.
Related questions
Question
Transcribed Image Text:Problem 3: Almost a priority queue. Design a data structure that supports the following
operations for almost a priority queue:
(i) FindSecondSmallest () which returns the second smallest item in the data structure.
(ii) Insert(x) which inserts item x to the data structure.
(iii) DeleteSecond Smallest() which removes the second smallest item from the data
structure.
Your data structure should implement the operation FindSecondSmallest () in O(1), and
the other two operations in O(logn), where n is the number of elements in the data
structure.
Expert Solution
This question has been solved!
Explore an expertly crafted, step-by-step solution for a thorough understanding of key concepts.
Step by step
Solved in 2 steps
