0
$\begingroup$

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

  1. Which data structure or combination of data structures would you use as representation for the SpecialContainer and how?

  2. 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?

Improve this question
$\endgroup$
2
  • $\begingroup$ Welcome to COMPUTERSCIENCE @SE. There seems to be a parameter n missing from find/popNthSmallest(sc). $\endgroup$ – greybeard Aug 5 '20 at 6:19
  • $\begingroup$ What's the context where you encountered this task? Please credit the source of all copied material. $\endgroup$ – D.W.♦ Aug 6 '20 at 4:23
0
$\begingroup$

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():
    1. Pop the root of the max-heap
    2. x := Pop the root of the min-heap
    3. Insert x into the max-heap
  • push(x):
    1. Push x into the max-heap
    2. y := Pop the root of the max-heap.
    3. Push y into the min-heap.
Improve this answer
$\endgroup$
6
  • 2
    $\begingroup$ This doesn't quite work because the operations on the min-heap will have $O(\log k)$ where $k$ is the total number of elements. That said, OP's original bounds are impossible (you could get linear time sorting simply by setting $n = 1$), so I think this solution is valid anyway. $\endgroup$ – orlp Aug 2 '20 at 17:28
  • $\begingroup$ @orlp, heap requires $O(\log n)$ for push/pop and $O(1)$ for peek (and findNthSmallest requires only peek), so, as far as I can tell, it matches the required complexity. $\endgroup$ – Dmitry Aug 2 '20 at 17:34
  • $\begingroup$ To make things unambiguous, a heap requires $O(\log s)$ for pop, where $s$ is the size of the heap. In popNthSmallest, which must have complexity $O(\log n)$ according to OP you call pop twice. Once on a heap with size $n$, so that is fine, but another time on a heap with size $k - n$, where $k$ is the total number of elements. That is not fine. Imagine if $k = 10^9$ and $n = 10$. The OP would expect $O(\log 10)$ but gets $O(\log (10^9 - 10))$ instead (abusing big O notation a bit). $\endgroup$ – orlp Aug 2 '20 at 17:37
  • $\begingroup$ @orlp, Ah, I see. I confused $n$'s. $\endgroup$ – Dmitry Aug 2 '20 at 17:38
  • 1
    $\begingroup$ If $n=2$ and you do push(3),push(2),push(1), in that order, we have $3,2,1$ in the max-heap. If we do findNthSmallest() it will return 3. $\endgroup$ – plop Aug 2 '20 at 17:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.