最小堆是如何创建的？

Question

在代码中给出了一个字符串流，我们返回了流中 k 个最长的字符串。我的问题是比较器是如何工作的？我知道我们正在使用匿名函数来覆盖比较方法来比较两个字符串的长度，但是这种比较如何创建最小堆？

public static List<String> topK(int k, Iterator<String> iter) {
PriorityQueue<String> minHeap = new PriorityQueue<>(k, new Comparator<String>() {
   public int compare(String s1, String s2) {
     return Integer.compare(s1.length(), s2.length());  
   }
});
while (iter.hasNext()) {
  minHeap.add(iter.next());
  if (minHeap.size() > k) {
    // Remove the shortest string. Note that the comparison function above
    // will order the strings by length.
    minHeap.poll();
  }
}
return new ArrayList<>(minHeap);
}

Answer 1

尝试用简单的语言概括

二叉堆是二叉队列背后的一种特殊的树型数据结构。在堆中，每个节点及其 child 节点都遵循一些共同的模式。例如，在最小堆中，所有 child 节点必须大于 parent 节点。因此，根节点拥有最小的数字。

在堆中，当堆中有任何更改（插入、删除、更新）时，堆将以某种方式重组，从而保持通用原则（例如，在上述情况下 parent 始终小于它的 children)。因此，当对堆进行某些操作时，会调用 heapify 操作。 SO对于min-heap，会调用一个min-heapify来维护原理。所以在 min-heapify 操作中，parents 将递归地与 child 节点进行比较，以检查哪个具有较低的值，以及 child 是否具有较低的值, 然后它将与 parents.

交换

现在在你的例子中，你只是实现了heapify操作的这个比较方法。因此，对于最大堆，您只需执行相反的操作（将更高的值设置为 parent）。此外，您可以根据自己的需要实现自定义比较方法。

要了解更多细节，您可以使用二进制堆进行搜索，那里可以找到很多好的资源。

Answer 2

来自Javadoc of PriorityQueue：

The head of this queue is the least element with respect to the specified ordering.

和PriorityQueue.poll()：

Retrieves and removes the head of this queue, or returns null if this queue is empty.

比较器按长度递增对元素进行排序，因此队列的头部是长度最小的元素。因此，当您调用 poll() 时，最短的字符串将从队列中移除。

如果弹出以仅在队列中保留最多 k 个项目，那么这些项目将是迄今为止从迭代器中取出的 k 个最长的项目。一旦迭代器耗尽，这些将是（最多）k 最长的项目。

最小堆是如何创建的？

How is the min heap being created?

java

heap