Consider the following problem: we want to implement ADT SpecialContainer which stores integer numbers and is similar to a PriorityQueue. This containter should support the following operatios:
-init(sc, n) – create a new, empty SpecialContainer sc. n is a positive integer number(will be used later – Theta(1) total complexity
-push(sc, x) – adds the integer number x to the SpecialContainer – O(log n) total complexity
-findNthSmallest(sc) – returns the nth smallest element from sc, where n is the number given to the init function – Theta(1) total complexity
-popNthSmallest(sc) – removes and returns the nth smallest element from sc – O(log n) total complexity
Which data structure or combination of data stuctures would you use as representation for the SpecialContainer and how?
Explain in short how would you implement each operation of the SpecialContainer and why the implementation fits the complexity requirement.
I was thinking about a combination of a heap and a hash map, but I don’t think if it works. Can somebody help me, please?