使用优先级队列对 java 中的元素进行排序

Question

我想在 Java 中使用优先队列对元素进行排序。

这是我的代码。这有什么问题吗？

import java.io.*;
import java.util.*;

class PQ {
    static class IntCompare implements Comparator<Integer>{
        @Override
        public int compare(Integer arg0, Integer arg1) {
            if(arg0 > arg1)
                return -1;
            else if(arg0 < arg1)
                return 1;
            else
                return 0;
        }
   }

    public static void main (String[] args) {
        int a[] = { 1, 3, 8, 5, 2, 6 };

        Comparator<Integer> c = new IntCompare();
        PriorityQueue<Integer> pq=new PriorityQueue<>(c);

        for(int i = 0; i < a.length; i++)
            pq.add(a[i]);

        System.out.println(pq);
    }
}

我的输出是：

8, 5, 6, 1, 2, 3

正确输出：

8, 6, 5, 3, 2, 1

Answer 1

您应该 poll() 所有元素，直到队列为空，然后将它们保存在某处以便进行排序。

Answer 2

尝试以下操作，列表包含按排序顺序排列的项目。 优先级键本身不会按排序顺序维护元素，它只是根据您对 PQ 的实现将顶部元素保持为最小值或最大值。

public static void main (String[] args) {
        int a[]={1,3,8,5,2,6};
        Comparator<Integer> c = new IntCompare();
        PriorityQueue<Integer> pq=new PriorityQueue<>(c);
        for(int i=0;i<a.length;i++)
            pq.add(a[i]);
        ArrayList<Integer> list  = new ArrayList<>();
        while(!pq.isEmpty()){
            list.add(pq.poll());
        }
        for(Integer i : list)
            System.out.println(i);
}

Answer 3

当您调用 System.out.println(pq) 时，会隐式调用 toString 方法。

PriorityQueue 的 toString 方法扩展自 AbstractCollection，

Returns a string representation of this collection. The string representation consists of a list of the collection's elements in the order they are returned by its iterator, enclosed in square brackets ("[]").

虽然 PriorityQueue 的 iterator 不能保证按特定顺序遍历：

The Iterator provided in method iterator() is not guaranteed to traverse the elements of the priority queue in any particular order.

因为队列基于 heap。

您可以一个一个地轮询元素以获取有序元素：

while (pq.size() != 0) {
    System.out.print(pq.poll() + ","); // 8,6,5,3,2,1,
}

使用优先级队列对 java 中的元素进行排序

sort the elements in java using priority queue

java

queue

priority-queue

comparable

comparator