代码之家 › 专栏 › 技术社区 › simpatico

如何根据列表的自然顺序创建PQ排序?

priority-queue collections java

simpatico · 技术社区 · 15 年前

我的SSCE:

public class ComparableItem implements Comparable<ComparableItem> {

    private final int itemNo;

    public ComparableItem(final int itemNo) {
        this.itemNo = itemNo;
    }

    @Override
    public int compareTo(ComparableItem o) {
        if (this.itemNo < o.itemNo) {
            return -1;
        } else if (this.itemNo > o.itemNo) {
            return 1;
        }
        return 0;
    }
}

这是一个证明问题的测试。创建PQ后代码中断。上面这几行是为了证明compareTo(..)定义的自然顺序是按预期工作的。打印PQ元素:14,9,15,5,6,3与预期的15,14,9,6,5,3。有人能解释一下为什么会这样吗?

import org.junit.Test;
import java.util.*;
import static org.junit.Assert.*;

public class CompTest{

@Test
public void aTest() {

    Integer[] order = {9, 3, 14, 15, 6, 5};
    List<ComparableItem> items = new ArrayList<ComparableItem>(order.length);
    for (int i = 0; i < order.length; i++) {
        items.add(new ComparableItem(order[i]));
    }

    List<ComparableItem> greater = new ArrayList<ComparableItem>();
    testCompare(items, items.get(3), greater, true);
    testCompare(items, items.get(2), greater, true);
    testCompare(items, items.get(0), greater, true);
    testCompare(items, items.get(4), greater, true);
    testCompare(items, items.get(5), greater, true);
    testCompare(items, items.get(1), greater, true);

    final PriorityQueue<ComparableItem> itemsQueue = new PriorityQueue<ComparableItem>(items);
    greater = new ArrayList<ComparableItem>();
    for (ComparableItem c : itemsQueue) {
        testCompare(itemsQueue, c, greater, false);
    }
}

public static void testCompare(final Collection<ComparableItem> items, final ComparableItem item, final List<ComparableItem> greater, boolean bigger) {
    final int exp = (bigger)? -1:1;
    for (ComparableItem c : items) {
        final int expected = c.equals(item) ? 0 : greater.contains(c) ? exp : exp*-1;
        assertEquals(expected, item.compareTo(c));
        assertEquals(expected * -1, c.compareTo(item));
    }
    greater.add(item);
}

}

new PriorityQueue<ComparableItem>(items);

创建包含指定集合中的元素。如果指定的集合是 SortedSet的实例或是另一个优先级队列,这个优先级队列将根据相同的命令。否则,这个优先权队列将根据元素的自然顺序。

1 回复 | 直到 15 年前

Stephen C 15 年前

我认为问题不在队列中,而在您测试它的方式上。尤其是 PriorityQueue.iterator() 国家:

返回此队列中元素的迭代器。迭代器不按任何特定顺序返回元素。

javadoc类说:

方法Iterator()中提供的迭代器不能保证以任何特定顺序遍历优先级队列的元素。如果需要有序遍历,请考虑使用Arrays.sort(pq.toArray())。