java - 如果我的比较器在忙于向上或向下冒泡时抛出异常，我的 PriorityQueue 会发生什么情况？

Question

我正在尝试按升序对整数对进行排序，如果一对整数的两个条目均严格小于另一对的条目，则将其视为小于另一对；如果其两个条目均严格大于另一对的条目，则将其视为大于另一对。所有其他情况都被认为是不可比较的。

我想要解决这个问题的方法是定义一个实现上述内容的Comparator，但会在无法比较的情况下抛出异常，并将其提供给PriorityQueue。当然，在插入一对时，优先级队列会进行多次比较，同时将新条目冒泡到堆中的正确位置，其中许多比较是可比较的。但是在冒泡过程中可能会遇到一个与这个新的pair无法比较的pair，就会抛出异常。如果发生这种情况，PriorityQueue 的状态会是什么？我试图插入的对是否会位于抛出异常之前的堆中最后一个位置？如果我使用PriorityQueue的remove(Object o)方法，PriorityQueue会恢复到一致的状态吗？

谢谢

Answer 1

如果您查看 PriorityQueue 源代码，当添加/提供新元素时，会在没有任何 try/catch 的情况下调用 .compare() 方法(这是在 siftUpUsingComparator() 中)，这是有道理的，因为 PriorityQueue 没有责任阻止您将不可比较的元素放入队列中。因此，您的比较器抛出的任何 RuntimeException 都会冒泡到您的调用代码。

这里更大的问题是，为什么您要尝试对按照您的定义“无法比较”的项目进行排序？这没有多大意义。如果这些项目属于同一类型，但既不大于也不小于另一个项目，则比较器应将它们返回为相等。 Comparator 的语义是这样的，“等于”并不意味着“具有相同的值”，而是“与被比较的元素具有相同的顺序” - 换句话说，当您希望两个项目在排序中彼此相邻时，您返回 equal (0)。