4

可能重复：
Java：由优先级队列组成的奇怪队列顺序

我厌倦了通过实现以下比较器将优先级队列变成队列：

  • 技巧：QueueComparator 通过始终返回 1 使 PriorityQueue 的行为类似于队列 (FIFO)
  • 由于优先级队列的“自然排序”在头部具有最少元素，并且传统比较器在第一个小于第二个时返回 -1，因此被破解的比较器始终返回 1，以便放置当前（最后一个）方格在尾部（递归）

这是代码：

import java.util.Comparator;
public class QueueComparator implements Comparator<Square>{
    public int compare(Square square1, Square square2)
    {
        return 1;
    }
}

但是由此产生的“队列”并没有使事情井井有条（FIFO）。为什么？

4

4 回答 4

9

问题是为什么要这样做？

首先，您的 Comparator 完全损坏了，因为它违反了以下基本约束：

sign(compare(a,b)) = - sign(compare(b,a))

和

compare(a,a) == 0

所以任何使用它的东西都可能会出现各种各样的结果，比如丢失条目、无限循环运行、抛出 stackoverflow ......

如果你想实现 aIDontGiveAShitComparator它应该一直返回 0 。所有依赖于 Comparator 的东西都应该能够处理。

什么命令结果仍然取决于执行。如果它将元素存储在列表中 FIFO 或 LIFO 是可能的，如果它存储在平衡树中，它可能会始终在一侧添加元素，从而导致树的重新平衡，这几乎会将所有内容混合在一起。

也许它使用了基于哈希的东西，在这种情况下，所有具有相同优先级的元素可能会按照它们的哈希值排序。

于 2012-10-04T07:44:42.077 回答
4

compareTo(a,b)通常应该返回-compare(b,a)，并且compareTo(a,a)应该返回零。你的比较器打破了这两个规则。

检查Javadoc。

于 2012-10-04T07:44:44.633 回答
4

嗯，这是一个黑客。因此，如果它不起作用，我不会太惊讶。

PriorityQueue的Javadoc说：

此队列的头部是相对于指定排序的最小元素。如果多个元素以最低值绑定，则头部是这些元素之一 - 绑定被任意打破。

好吧，你有它。如果您的比较器为所有元素对返回相同的值，那么您只有平局。所以队列顺序确实是任意的。

于 2012-10-04T07:39:51.907 回答
0

优先级队列的常见实现是使用二叉堆完成的（默认的 Java 实现也是如此）。比较器仅用于保持堆属性（节点始终大于/等于（或小于/等于）其所有子节点）为真。如果比较器将始终返回 1，则 PriotityQueue 的行为可能会导致在插入后尝试恢复堆属性时出现意外行为，但不会以 FIFO 队列结束。

请注意，BinaryHeap 中没有真正的“尾巴”，因为它是按树组织的。最后应该出现的元素是叶节点，但不是“最后”。

于 2012-10-04T07:45:15.500 回答