获取PriorityQueue中的第k个最小元素（Java）

Question

为了好玩/Java实践，我做了以下问题：

编写一个方法，该方法将整数的优先级队列作为输入，并输出最小整数。该方法不应更改传入的优先级队列的内部状态。您只能使用一个队列或堆栈作为额外数据。不允许使用其他数据结构<代码>k为1索引（k=1表示最小值）。

获取kth元素很简单：只需删除k次，因为它是优先级队列。我想我可以弹出，将元素放在堆栈上进行存储，然后在完成后将它们添加回队列。不过这不起作用，因为元素在优先级队列中的顺序不同。

以下是我的好奇心代码：

public int kthSmallest(PriorityQueue<Integer> pq, int k) {
    Stack<Integer> s = new Stack<Integer>();

    for (int i = 1; i <= k; ++i) {
            s.push(pq.remove());
    }

    int kthValue = s.peek();

    while (!s.empty()) {
        pq.add(s.pop());
    }

    return kthValue;
}

那么，如何在保持优先级队列的内部状态的同时做到这一点呢？

P、 你可以自己在这里查看问题

Answer 1

许多提示已经陈述，我会保持我的回答简短：

您正在处理来自给定对象的方法调用，而您对此一无所知。你不知道是否使用了一个奇怪的比较器来比较队列中的整数（例如，一个表示所有事物都相等并且总是返回0的比较器）。这就是为什么在任何情况下都不应该修改给定对象（就像使用轮询/添加一样）。

在这种情况下，为了解决这个问题，您可以使用缓冲区对象（如问题中所述，队列或堆栈（我使用了与给定队列类似的队列）来使用您选择的比较器，并通过将给定队列添加到缓冲区对象来缓冲它。

我在pastebin的解决方案，因为我没有任何扰流板标签：-（

Answer 2

你为什么要搬走？不需要修改传入的数据结构，这就是算法失败的原因。这只不过是一个迭代器/访问者。您只需遍历队列并维护一个最小数字的列表/数组。

还要注意，您认为队列中第k个最小整数与优先级中删除的数字相同的假设不一定正确。优先级队列！=堆在这个例子中，我可能有一个整数的优先级队列，每个整数都有一个优先级字段。

class Node<Integer>
   Integer data;
   int priority;
}

class PriorityQueue {
   List<Node> nodes;

   Integer getHighestPriority() { 
      int maxPriorityIndex = 0;
      for(int i=0; i< nodes.size(); i++) {
      if(n.priority > maxPriority) {
           maxPriorityIndex = nodes.get(i);
      }
      return nodes.get(maxPriorityIndex);
   }
}

Answer 3

关于底层状态，您无法保证任何东西：优先级队列（PriorityQueue）唯一的顺序概念是由您在创建它时指定的比较器（或其元素的自然顺序）提供的。作为用户，您对此一无所知，只要队列的行为符合基于其规范的预期，那么元素的存储方式就不会有任何区别。