Сортировать элементы в java с использованием очереди приоритетов
Я хочу отсортировать элементы с помощью очереди приоритетов в 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
Ответы 3
Вы должны poll() все элементы, пока очередь не опустеет, и сохранить их где-нибудь, чтобы они были упорядочены.
Попробуйте следующее: список содержит элементы в отсортированном порядке. Ключ приоритета сам по себе не поддерживает элементы в отсортированном порядке, он просто сохраняет верхний элемент как минимум или максимум в зависимости от вашей реализации 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);
}
Когда вы вызываете System.out.println(pq), метод toString вызывается неявно.
Метод toStringPriorityQueue происходит от 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 ("[]").
Хотя iteratorPriorityQueue не гарантирует прохождение в определенном порядке:
The Iterator provided in method iterator() is not guaranteed to traverse the elements of the priority queue in any particular order.
поскольку очередь основана на куча.
Вы можете опросить элементы один за другим, чтобы получить упорядоченные элементы:
while (pq.size() != 0) {
System.out.print(pq.poll() + ","); // 8,6,5,3,2,1,
}
Ваш PriorityQueue упорядочен,
toStringпросто выводит их в произвольном порядке (как четко указано в Javadoc). Также подумайте об использованииComparator.reverseOrder()вместо изобретения велосипеда.