如何在方法调用之前将PriorityQueue恢复为其初始状态？

Question

我在做练习题练习IT
Kth最小

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

我的高级伪思维是，由于PriorityQueue已经充当了最小堆，因此从Java
PriorityQueue中
，我真正要做的（我的算法）是：

1. 从PriorityQueue中删除k个元素

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

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

4. 从堆栈中弹出所有元素，然后将它们重新添加到PriorityQueue中

5. 返回第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。这是因为堆栈是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’变量从type
int更改为Integer。程序的正确性无关紧要，但是注意自动装箱是一个好习惯。通用类型（如集合）使用 装箱的
整数。这是一个存储原始整数的对象。将装箱的整数分配给某种类型的东西int要求将其拆箱，即重新变成int原始类型。这没什么大不了的，只不过您要立即将此值再次重新添加到集合中。由于您已将其拆箱为原始文件int，因此需要将其重新装箱到Integer再次，这需要系统创建一个对象来存储它。由于您所要做的就是将值取出并放回集合中，因此最好在Integer此处使用一个值，以避免拆箱和装箱价值，因为它不是真正需要的。