Container with findNthSmallest in O(1) 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 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 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?
As pointed out by orlp, it's impossible to do in $O(\log n)$ time. However, we can do this in $O(\log N)$ time, where $N$ is the total number of items.
You can do this with 2 Heaps:
The first heap is a max-heap with the smallest $n$ elements. Its root is the $n$-th smallest element.
The second one is the min-heap with the rest of the elements. Its root is the $n+1$-th smallest element.
When max-heap has less than $n$ elements, the operations are trivial. Otherwise:

findNthSmallest() - it's just the root of the max-heap. O(1) time
popNthSmallest():

Pop the root of the max-heap
x := Pop the root of the min-heap
Insert x into the max-heap


push(x):

Push x into the max-heap
y := Pop the root of the max-heap.
Push y into the min-heap.