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

Question

我在做一道练习题Practice IT Kth Smallest

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

我更高层次的伪思维是因为 PriorityQueue 已经作为一个最小堆，来自 Java PriorityQueue ，我真正需要做的(我的算法)是:

1. 从PriorityQueue中取出k个元素

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

3. 将移除的 k 个元素插入堆栈(堆栈以便我可以按相同顺序添加元素)

4. 从 Stack 中弹出所有元素，然后将它们重新添加回 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 的状态。例如，当传入一个 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;
      }
}

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