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

问题描述

我正在做一个练习题练习IT第K个最小的

这个问题基本上是在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个最小值

这里是所有的代码：

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

当我运行程序时，我得到所有正确的输出，以kth为最小，但我无法恢复我的PriorityQueue的状态。例如，当通过aQQ的PriorityQueue时，通过ak进入：

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 。对于您的程序的正确性无关紧要，但是注意自动拳击是一个很好的习惯。通用类型，如集合，使用整数。这是存储原始整数的对象。将一个带框的整数分配给类型为 int 的东西，需要将其取消装箱，即转回到 int 原语。这不是一件大事，除了你马上将这个值重新加入到一个集合中。由于您已经将其解包装成原始的 int ，所以需要重新装入 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屋！