Сортировка очереди приоритетов в Java

Я пытался вставить целые числа в PriorityQueue, и я знаю, что:

Если никакой компаратор не указан при построении PriorityQueue, то по умолчанию используется компаратор для типа данных, хранящихся в очереди. Компаратор по умолчанию закажет очередь в порядке возрастания

Однако вывод, который я получаю, не находится в отсортированном порядке. Вывод после запуска приведенного ниже кода: [2, 4, 8, 6]

public static void main(String args[]) {
    PriorityQueue<Integer> q = new PriorityQueue<Integer>(10);
    q.offer(4);
    q.offer(2);
    q.offer(8);
    q.offer(6);

    System.out.print(q);
}

Может кто-нибудь объяснить, почему?

Ответы

Ответ 1

A PriorityQueue - это то, что называется бинарной кучей. Он упорядочен/отсортирован только в том смысле, что первый элемент является наименьшим. Другими словами, он заботится только о том, что находится в передней части очереди, остальные "заказываются", когда это необходимо.

Элементы упорядочиваются только по мере их удаления, т.е. удаляются из очереди с помощью poll(). Именно по этой причине PriorityQueue удается получить такую ​​хорошую производительность, поскольку она не делает больше сортировки, чем нужно в любое время.

Если вы хотите знать, как работают кучи, я рекомендую эту лекцию MIT на кучи.

Ответ 2

Когда вы вызываете System.out.print() на свой PriorityQueue, он не будет poll() ваших элементов из него, а вызовет toString(). PriorityQueue не реализует toString(), поэтому он будет toString() из AbstractCollection, который будет вызываться:

public String toString() {
    Iterator<E> i = iterator();
if (! i.hasNext())
    return "[]";

StringBuilder sb = new StringBuilder();
sb.append('[');
for (;;) {
    E e = i.next();
    sb.append(e == this ? "(this Collection)" : e);
    if (! i.hasNext())
    return sb.append(']').toString();
    sb.append(", ");
}
}

Как вы можете видеть, этот метод только повторяет PriorityQueue. Как вы можете видеть в PriorityQueue javadoc:

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

Если вы хотите использовать PriorityQueue, поскольку он предназначен для использования, вы должны poll() выполнить каждое значение и напечатать его:

while (!q.isEmpty()) {
    Integer i = q.poll();
    System.out.println(i);
}

Вывод:

2
4
6
8

Ответ 3

Это потому, что java.util.PriorityQueue реализует двоичную кучу.

К сожалению, нет простого способа сортировки PriorityQueue. Если вы poll() объекты, пока очередь не будет пустой, элементы будут в порядке сравнения. Поэтому, когда я столкнулся с аналогичной проблемой, я реализовал свой собственный класс кучи, который позволяет мне сортировать элементы после факта; который я использую для верхнего N-списка большого количества элементов.

(Поскольку я создал класс на задании, у меня нет права публиковать его здесь, но он в значительной степени моделируется после python heap.py, поэтому есть хороший источник вдохновения)

Ответ 4

Неограниченная очередь приоритетов основана на priority heap

Priority Queue.Offer() метод использует siftUpComparable() внутренне для вставки элементов при передаче без компаратора

siftUpComparable сравнивает текущий элемент со всеми элементами в родительских позициях (int i = paramInt - 1 >>> 1;), пока не будет выполнено условие кучи

siftUpComparable Алгоритм в двух словах (если реализован через массив Root = index 0):

1.Add the element to the bottom level of the heap.
2.Compare the added element with its parent; if they are in the correct order, stop.
3.If not, swap the element with its parent and return to the previous step.

Код Java

  private void siftUpComparable(int paramInt, E paramE)
  {
    Comparable localComparable = (Comparable)paramE;
    while (paramInt > 0)
    {
      int i = paramInt - 1 >>> 1;
      Object localObject = this.queue[i];
      if (localComparable.compareTo(localObject) >= 0) {
        break;
      }
      this.queue[paramInt] = localObject;
      paramInt = i;
    }
    this.queue[paramInt] = localComparable;
  }

В вашем примере:

q.offer(4); → Вставки 4

Result: PQ[0]=4

q.offer(2); → siftUpComparable сравнивается с 4 по 2 и места подкачки (сравнения в родительских локациях)

Result: PQ[0]=2,PQ[1]=4

q.offer(8); → siftUpComparable Сравнивает 8 и 2 (так как 2 находится в исходном местоположении)

Result: PQ[2]=8

q.offer(6);: → siftUp Сравнивает 6 с 4 (Родитель местоположения 3 - это местоположение 1 согласно логике paramInt - 1 >>> 1;)

Result: PQ[3]=6

Финал PQ=[2, 4, 8, 6]