java - 如何创建根据列表的自然顺序排序的 PQ？

Question

我的 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);

Creates a PriorityQueue containing the elements in the specified collection. If the specified collection is an instance of a SortedSet or is another PriorityQueue, this priority queue will be ordered according to the same ordering. Otherwise, this priority queue will be ordered according to the natural ordering of its elements.

Answer 1

我认为问题不在于队列，而在于您测试它的方式。特别是 PriorityQueue.iterator() 的 javadoc状态:

Returns an iterator over the elements in this queue. The iterator does not return the elements in any particular order.

类 javadoc 是这样说的:

The Iterator provided in method iterator() is not guaranteed to traverse the elements of the priority queue in any particular order. If you need ordered traversal, consider using Arrays.sort(pq.toArray()).