How to restore the PriorityQueue to its initial state before the method call?

Question

I am doing a practice problem Practice IT Kth Smallest

This problem is basically you're passed in a PriorityQueue and a certain k, and you are to return the kth smallest value in that PriorityQueue. You are also to restore the PriorityQueue to its initial state and can use one stack or queue as an auxiliary data structure.

My higher level pseudo thinking is that because the PriorityQueue acts as a min heap already, from Java PriorityQueue, all I really have to do (my algorithm) is:

1. Remove k elements from the PriorityQueue

2. Store the kth smallest value as a local variable

3. Push removed k elements onto a Stack (Stack so I can add elements in the same order)

4. Pop all the elements from the Stack and re add them back into the PriorityQueue

5. Return the kth smallest value

Here is the code to do all of that:

public int kthSmallest(PriorityQueue<Integer> pQ, int k) {
    if(k <= 0 || k > pQ.size()) {
           throw new IllegalArgumentException();
    } else {
         Stack<Integer> aux = new Stack<Integer>();
         int kThSmallest = -1;
         for(int c=0;c<k;c++){
               int element = pQ.remove();
               if(c == k-1) 
                   kThSmallest = element;
               aux.push(element);
          }
          while(!aux.isEmpty())
              pQ.add(aux.pop());
         return kThSmallest;
      }    
}

When I run the program I get all the right outputs, in terms of kth smallest, but I can't restore the state of my PriorityQueue. For example, when passing in a PriorityQueue of:

[-3, 9, 17, 22, 42, 81] with a k of 3

... my algorithm produces the right result, 17, but it changes the state of the PriorityQueue to [-3, 17, 9, 81, 22, 42], which is unexpected.

I thought about making a copy of the PriorityQueue but that violates one the conditions, "you can use one stack or queue as an auxiliary data structure".

How can I go about restoring the state of the PriorityQueue?

Answer 1

Two things need to be adjusted in your implementation. First, you should use a queue, rather than a stack, as your auxiliary data structure. The pushing items into a stack and then popping them back out will result in them being added back into your priority queue in reverse order. If they come out of the priority queue as 1, 2, 3, they'll be added back to the priority queue as 3, 2, 1. This is because stacks are a LIFO (Last in, first out) data structure. You want to use a queue as your auxilary data structure because it is a FIFO (First in, first out) data structure, so it will preserve the same order.

Second, you only pull the first k elements out of the priorty queue. I would recommend draining the entire queue, so that you're adding all of the elements back into the queue in the order they came out, rather than just some.

In other words, I would adjust your program as follows:

public int kthSmallest(PriorityQueue<Integer> pQ, int k) {
    if(k <= 0 || k > pQ.size()) {
           throw new IllegalArgumentException();
    } else {
         Queue<Integer> aux = new ArrayDeque<Integer>();
         int kThSmallest = -1;
         for(int c=0;c<pQ.size();c++){
               Integer element = pQ.remove();
               if(c == k-1) 
                   kThSmallest = element;
               aux.add(element);
          }
          while(!aux.isEmpty())
              pQ.add(aux.remove());
         return kThSmallest;
      }
}

Note: I changed the 'element' variable in your program from type int to Integer. It doesn't matter for the correctness of your program, but it is a good habit to pay attention to auto-boxing. Generic types, like collections, use boxed integers. This is an object that stores the primitive integer. Assigning a boxed integer to something of type int requires that it be unboxed, i.e. turned back into an int primitive. This isn't a big deal, except that you're immediately adding this value back into a collection again. Since you've unboxed it into a primitive int, it needs to be boxed back into an Integer again, and that requires the system to create an object to store it in. Since all you're doing with the value is taking it out of and putting it back into collections, it's better to use an Integer value here, to avoid unboxing and boxing the value, since it isn't really needed.