1

我正在PriorityQueue我的程序中实现一个。为此，我也实施了compareTo(). 当compareTo()我执行时，正在调用add()，这是预期的。但是当我执行时也会调用它poll()。
我认为poll()的功能只是去除头部。为什么需要调用compareTo()？

4

2 回答 2

3

优先级队列的实现方式通常是通过堆来完成的。部分poll()ing需要重组堆，这需要堆来比较元素......因此compareTo()。这只是一个猜测（即我没有深入研究源代码来验证我的说法）。

如果您有兴趣，可以快速搜索如何使用堆实现优先级队列：http: //pages.cs.wisc.edu/~vernon/cs367/notes/11.PRIORITY-Q.html#imp

实际上只是为了好玩，我会以一种不严谨的方式描述它是如何工作的。堆是满足堆属性的树：父母总是小于或等于他们的孩子（最小堆）或父母总是至少和他们的孩子一样大（最大堆）。PriorityQueue是一个minheap所以poll()删除根（确保您理解这一点）。但是如果你去掉根，树会发生什么？它不再是一棵树......所以他们解决这个问题的方法是将树的根移动到一个叶子节点（可以在不破坏树/使堆属性无效的情况下拔出它），并将其他一些节点放入根。但是您将哪个节点放入根目录？直觉上你可能会认为他们会放置根的左子或右子（那些“几乎和原始根一样小”）。你可以这样做，但是你需要修复以那个孩子为根的子树（而且代码很丑）。相反，它们（从概念上）做同样的事情，但做起来略有不同，以使代码更好。尤其是，他们采摘叶节点并将其粘贴在根中（通常您交换根和叶节点以同时执行这两个步骤）。但是，那不再必须满足堆属性（我们卡在根中的叶节点可能非常大！）。为了解决这个问题，你“冒泡”新的根，直到你把它放到正确的位置。具体来说，您将新根与左右子节点进行比较，并不断交换（如果父节点大于至少一个子节点），直到满足堆属性。请注意，这种交换确实会导致有效的堆（您可以证明这一点，但它很直观）。

于 2012-11-18T12:45:56.387 回答
2

一切都在JavaDoc中（重点是我的）：

基于优先级堆的无界优先级队列。

在你的源代码中poll()你会发现：

public E poll() {
    //...
    if (s != 0)
        siftDown(0, x);
    return result;
}

在哪里siftDown()：

/**
 * Inserts item x at position k, maintaining heap invariant by
 * demoting x down the tree repeatedly until it is less than or
 * equal to its children or is a leaf.
 * [...]
 */
private void siftDown(int k, E x) {
    if (comparator != null)
        siftDownUsingComparator(k, x);
    else
        siftDownComparable(k, x);
}

JavaDoc 上的注释siftDown()至关重要，请仔细阅读。基本上，底层的实现PriorityQueue使用了一个堆，每次通过轮询修改它时都必须对其进行重组。

你为什么要为此烦恼？compareTo()应该是轻量级、幂等且无副作用的方法，例如equals(). 你不应该对它施加任何限制。

于 2012-11-18T12:45:43.570 回答