如何将 PriorityQueue 恢复到方法调用前的初始状态？

Question

这个问题基本上是你传入了一个 PriorityQueue 和一个特定的 k，你要 return 该 PriorityQueue 中的第 k 个最小值。你也要把PriorityQueue恢复到初始状态，可以使用一个stack或者queue作为辅助数据结构。

我更高层次的伪思维是，因为 PriorityQueue 已经充当最小堆，从 Java PriorityQueue，我真正需要做的（我的算法）是：

从 PriorityQueue 中移除 k 个元素
将第k小的值存为局部变量
将移除的 k 个元素推入堆栈（堆栈以便我可以按相同顺序添加元素）
从 Stack 中弹出所有元素，然后将它们重新添加回 PriorityQueue
Return第k小值

这是执行所有这些操作的代码：

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;
      }    
}

当我运行程序时，我得到了所有正确的输出，就第 k 个最小值而言，但我无法恢复我的 PriorityQueue 的状态。例如，当传入一个 PriorityQueue 时：

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

...我的算法产生了正确的结果 17，但是它将 PriorityQueue 的状态更改为 [-3, 17, 9, 81, 22, 42]，这是意外的。

我考虑过制作 PriorityQueue 的副本，但这违反了一个条件，"you can use one stack or queue as an auxiliary data structure"。

我怎样才能恢复 PriorityQueue 的状态？

Answer 1

您的实施需要调整两件事。首先，您应该使用队列而不是堆栈作为您的辅助数据结构。将项目推入堆栈然后将它们弹出将导致它们以相反的顺序被添加回您的优先级队列。如果它们作为 1, 2, 3 从优先级队列中出来，它们将作为 3, 2, 1 添加回优先级队列。这是因为堆栈是一种 LIFO（后进先出）数据结构。你想使用队列作为你的辅助数据结构，因为它是一个 FIFO（先进先出）数据结构，所以它会保持相同的顺序。

其次，你只从优先队列中取出前k个元素。我建议清空整个队列，这样您就可以按照元素出现的顺序将所有元素添加回队列，而不是只添加一些元素。

换句话说，我会调整你的程序如下：

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;
      }
}

注意： 我将您程序中的 'element' 变量从类型 int 更改为 Integer。这对你程序的正确性无关紧要，但注意自动装箱是一个好习惯。通用类型，如集合，使用 boxed 整数。这是一个存储原始整数的对象。将装箱整数分配给 int 类型的东西需要将其拆箱，即变回 int 原语。这没什么大不了的，只是您要立即将此值再次添加回集合中。由于您已将其拆箱为原始 int，因此需要再次将其装箱回 Integer，这需要系统创建一个对象来存储它。由于您所做的一切值是将其取出并放回集合中，最好在此处使用 Integer 值，以避免对值进行拆箱和装箱，因为它并不是真正需要的。

如何将 PriorityQueue 恢复到方法调用前的初始状态？

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

java

algorithm

priority-queue

data-structures