Consider the following problem: we want to implement ADT SpecialContainer which stores integer numbers and is similar to a PriorityQueue. This container should support the following operations:
init(sc, n)- create a new, empty SpecialContainer
nis a positive integer number (will be used later) - $\Theta(1)$ total complexity
push(sc, x)- adds the integer number
xto the SpecialContainer - $O(\log n)$ total complexity
findNthSmallest(sc)- returns the
nth smallest element from
nis 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 structures 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?