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 SpecialContainersc
.n
is a positive integer number (will be used later) - $\Theta(1)$ total complexity
push(sc, x)
- adds the integer numberx
to the SpecialContainer - $O(\log n)$ total complexity
findNthSmallest(sc)
- returns then
th smallest element fromsc
, wheren
is the number given to the init function - $\Theta(1)$ total complexity
popNthSmallest(sc)
- removes and returns then
th 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?
n
missing fromfind
/popNthSmallest(sc)
. $\endgroup$ – greybeard Aug 5 '20 at 6:19