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

Question

我正在做一个练习题，练习它

这个问题基本上是在PriorityQueue和某个k中传递，然后返回该PriorityQueue中的第k个最小值。您还需要将PriorityQueue恢复到其初始状态，并可以使用一个堆栈或队列作为辅助数据结构。

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

>

从PriorityQueue中删除k个元素

将第k个最小值存储为局部变量

将删除的k个元素推到堆栈上（堆栈以便我可以按相同顺序添加元素）

从堆栈中弹出所有元素，并将其重新添加回PriorityQueue

返回第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时：

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

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

我想过制作PriorityQueue的副本，但这违反了一个条件，“您可以使用一个堆栈或队列作为辅助数据结构”。

如何恢复PriorityQueue的状态？

Answer 1

在您的实现中需要调整两件事。首先，应该使用队列而不是堆栈作为辅助数据结构。将项目推入堆栈，然后将其弹出将导致它们以相反的顺序添加回优先级队列。如果它们作为1、2、3从优先级队列中出来，它们将作为3、2、1添加回优先级队列。这是因为堆栈是后进先出的数据结构。您希望使用队列作为辅助数据结构，因为它是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。这与程序的正确性无关，但注意自动装箱是一个好习惯。泛型类型（如集合）使用装箱整数。这是一个存储基元整数的对象。将装箱整数赋给int类型的某个对象需要取消装箱，即返回为int原语。这没什么大不了的，只是你会立即将这些价值重新添加到收藏中。由于您已将其解绑到一个基元int中，因此需要再次将其装箱到整数中，这需要系统创建一个对象来存储它。由于您对该值所做的一切都是将其从集合中取出并放回集合中，因此最好在此处使用一个整数，以避免对该值进行拆箱和装箱，因为实际上并不需要它。