java - PriorityQueue.poll() 调用 compareTo()？

Question

我正在我的程序中实现一个PriorityQueue。为此，我还实现了 compareTo()。 compareTo() 在我执行 add() 时被调用，这是预期的。但是当我执行poll()的时候也会调用。
我以为poll()的功能只是去掉人头而已。为什么需要调用 compareTo()？

Answer 1

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

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

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