最小堆是如何创建的？

问题描述：

在代码中给出一串字符串，我们返回流中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); 
}

您是否阅读过PriorityQueue的javadoc？ https://docs.oracle.com/javase/9/docs/api/java/util/PriorityQueue.html –

很难理解你在问什么。 “这个比较如何创造一个最小的堆”这个问题是不合情理的。比较*不会创建最小堆。 'PriorityQueue'代码通过使用您提供的比较器来订购堆中的项目来创建最小堆。请澄清你的问题。 –

答

从Javadoc of PriorityQueue：

这个队列的头是相对于指定的排序的最小元素。

而且PriorityQueue.poll()：

获取并移除此队列的头，或者返回null，如果此队列为空。

比较器通过增加长度来排序元素，所以队列的头部是长度最小的元素。因此，当您调用poll()时，最短的字符串将从队列中移除。

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

答

试图在容易句话来概括

二进制堆是二进制队列后面一种特殊类型的树的数据结构。在堆中，每个节点及其子节点遵循一些常见模式。例如，在最小堆中，所有子节点都必须大于父节点。因此，根节点保持最小的数量。

在堆中，当堆中有任何改变（插入，删除，更新）时，堆以某种方式进行重构，从而保持共同原则（例如，在上述情况下，父始终保持始终小于其子女）。所以当在堆上完成一些操作时，会调用heapify操作。对于最小堆来说，最小堆积将被称为维持原则。因此，在最小heapify操作中，将父节点与子节点进行递归比较，以检查哪个节点的值较低，如果孩子的值较低，则将与父节点交换。

现在在你的情况下，你只是实现heapify操作的比较方法。所以对于最大堆，你只需要做相反的事情（设置更高的值作为父母）。此外，您可以通过满足您自己的需求来实现自定义比较方法。

要了解更多详细信息，您可以使用二进制堆进行搜索，并且您可以找到很多优秀的资源。

最小堆是如何创建的？

相关推荐