Приоритетная очередь не поддерживает порядок сортировки

Приоритетная очередь не поддерживает порядок сортировки Я неправильно использую Comparable? Выводится неверный порядок сортировки?

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]

Сортируется только первая запись. Из javadoc для PriorityQueue `Итератор, предоставленный в методе iterator (), и Spliterator, предоставленный в методе spliterator (), не гарантируют прохождение элементов очереди приоритетов в каком-либо конкретном порядке. Если вам нужен упорядоченный обход, рассмотрите возможность использования Arrays.sort (pq.toArray ()).

Peter Lawrey 10.08.2018 15:22
2
1
1 993
3
Перейти к ответу Данный вопрос помечен как решенный

Ответы 3

Ответ принят как подходящий

В очереди с приоритетом единственная гарантия, что у вас есть, - это то, что голова является самым низким (или самым большим, в зависимости от вашего сравнения). Внутренняя структура не обязательно представляет собой отсортированный список. Собственно, в Java это куча:

PriorityQueue

An unbounded priority queue based on a priority heap.

Однако, если вы выполните цикл, в котором poll() является первым элементом, затем распечатайте его снова и снова, пока очередь приоритетов не станет пустой. Элементы должны быть напечатаны от самого низкого до самого большого элемента.

В PriorityQueue.toString() такой гарантии нет: AbstractCollection.toString говорит: «Строковое представление состоит из списка элементов коллекции в том порядке, в котором они возвращаются его итератором»; а PriorityQueue говорит: «Итератор, предоставленный в методе iterator (), не гарантирует обход элементов очереди с приоритетами в каком-либо определенном порядке». То, что нижний элемент появляется первым, это просто деталь реализации.

Andy Turner 10.08.2018 15:10

Приоратная очередь не гарантирует ordering. Используемая внутренняя структура данных - Heap. Но всякий раз, когда вы опрашиваете, он возвращает элемент в порядке приоритета. Например, приведенный ниже код:

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

Дает вам результат:

1 ,5 ,8 ,9 ,19 

Вы неправильно реализуете Comparable: это общий класс, поэтому вам следует указать параметры типа. Я полагаю, вам нужен Comparable<A>.

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

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

  // ...
}

Это не изменит вывод вашего кода, это просто избавит от приведений и предупреждений.

Кроме того, не сравнивайте целые числа с помощью вычитания, так как это не обрабатывает переполнения: используйте Integer.compare:

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

Другие вопросы по теме