Внутренняя сортировка PriorityQueue

Question

Я не могу понять внутреннюю сортировку, которая происходит в PriorityQueue:

import java.util.*;

public class TryME {
    public static void main(String args[]) {
        PriorityQueue<Integer> q = new PriorityQueue<Integer>();
        q.add(3);
        System.out.print(q);
        System.out.print("");
        q.add(1);
        System.out.print(q);
        System.out.print("");
        q.add(9);
        System.out.print(q);
        System.out.print("");
        q.add(6);
        System.out.print(q);
        System.out.print("");
        q.add(2);
        System.out.print(q);
        System.out.print("");
    }
}

Вывод:

[3][1, 3][1, 3, 9][1, 3, 9, 6][1, 2, 9, 6, 3]

На чтооснова это сортировка происходит?

Answer 1

Очередь приоритетов реализована в виде кучи, где все дочерние элементы для определенного узла имеют более низкий приоритет, чем его родительский элемент, но не обязательно его дочерние элементы.

Элементы хранятся в массиве (я подозреваю) следующим образом:

Для каждого узла дочерние элементы хранятся в 2 * pos и 2 * pos + 1. Таким образом, для [1, 2, 9, 6, 3]:

element 1 (value 1), children are 2 and 9.
element 2 (value 2), children are 6 and 3
element 3 (value 9), 4 (value 6) and 5 (value 3) have no children...

При удалении из очереди родительский узел заменяется одним из дочерних элементов с наивысшим приоритетом, который снова заменяется одним из его дочерних элементов и т. Д. (Операция очень оптимальная, работает только O (log n) время) Например:

[1, 2, 9, 6, 3]
[2, 9, 6, 3]
[3, 9, 6]
[6, 9]
[6]

Список очень сильно отсортирован, он только в куче, что не так заметно при печати нашего списка.

Answer 2

Javadoc говорит:

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

Если вы выполните

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

Вы увидите, что элементы действительно отсортированыправильно.

Answer 3

A PriorityQueue поддерживает вещи в порядке приоритета.Первый элемент, который вы извлекаете, является наивысшим приоритетом.Вероятность состоит в том, что это реализовано с использованием структуры данных кучи , которая предоставляет данные в порядке, но без полной сортировки (это позволяет более эффективно вставлять и удалять, чем каждый раз повторять содержимое).

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

Answer 4

В принципе, это не отсортировано. Реализации приоритетных очередей обычно амортизируют стоимость сортировки - они прилагают минимальные усилия, необходимые для обеспечения того, чтобы элементы были получены в правильном порядке. Он частично сортируется каждый раз, когда элемент извлекается настолько, чтобы выбрать элемент с наивысшим приоритетом. Очередь никогда не сортируется полностью.

Вместо вывода всей очереди, если вы позвоните по номеру poll(), чтобы извлечь числа, вы вернете их в том порядке, в котором ожидаете.

Answer 5

Я ничего не делал в Java в течение последних 7 лет, но, скорее всего, это что-то вроде heap .

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