如何在方法调用之前将 PriorityQueue 恢复到其初始状态? [英] How to restore the PriorityQueue to its initial state before the method call?

问题描述

我正在做一个练习题练习 IT Kth 最小

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

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.

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

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. 从 PriorityQueue 中移除 k 个元素

1. Remove k elements from the PriorityQueue

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

Store the kth smallest value as a local variable

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

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

从 Stack 中弹出所有元素并将它们重新添加回 PriorityQueue

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

返回第 k 个最小值

这是完成所有这些的代码:

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

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

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

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

... 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.

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

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".

如何恢复 PriorityQueue 的状态?

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

推荐答案

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

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.

其次，你只从优先队列中取出前 k 个元素.我建议排空整个队列，以便您按照它们出现的顺序将所有元素重新添加到队列中，而不仅仅是一些.

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

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

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.

这篇关于如何在方法调用之前将 PriorityQueue 恢复到其初始状态?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！