优先级队列未维护排序顺序

Question

优先级队列未维护排序顺序我是否未正确执行？输出时出现错误的排序顺序？

import java.util.PriorityQueue;

    class A implements Comparable 
    {
        int i;
        A(int i)
        {
            this.i =  i;

        }
        public int compareTo(Object obj)
        {
            return i - ((A)obj).i;
        }
        public String toString()
        {
            return Integer.toString(i);
        }

    }
    class Manager11
    {
        public static void main(String[] args) 
        {
            PriorityQueue pq =  new PriorityQueue();
            pq.add(new A(9));
            pq.add(new A(5));
            pq.add(new A(8));
            pq.add(new A(19));
            pq.add(new A(1));

            System.out.println(pq);
        }
}

产出：[1, 5, 8, 19, 9]

Answer 1

您没有正确实现Comparable：它是一个泛型类，因此您应该指定类型参数。我想你想要可比的

class A implements Comparable<A> {
  // ...

  @Override public int compare(A other) {
    return i - other.i;  // Cast is no longer required.
  }

  // ...
}

这不会改变代码的输出，只会消除强制转换和警告。

此外，不要使用减法比较int，因为这不会处理溢出：使用Integer.compare：

return Integer.compare(i, other.i);

Answer 2

隐修会队列不保证排序。它使用的内部数据结构是Heap。但无论何时轮询，它都会按优先级顺序返回元素。例如下面的代码：

for (int i = 0; i < 5; i++) {
    System.out.print(pq.poll() + " ,");
}

为您提供以下输出：

1 ,5 ,8 ,9 ,19 

Answer 3

在优先级队列中，唯一的保证是头是最低的（或最大的，取决于您的比较）。内部结构不一定是排序列表。实际上，在Java，它是一堆：

优先队列

基于优先级堆的无限优先级队列。

但是，如果执行轮询（）第一项的循环，则将其重复打印，直到优先级队列为空。元素应该从最低到最大的元素打印。