Предположим, что вы предлагаете услуги трем разным людям, стоящим перед вами. Третий человек оказывается вашим другом. Услуга должна быть обслужена в порядке очереди. При использовании принципа «первым пришел — первым обслужен» первый человек имеет наибольший приоритет; второй человек имеет больший приоритет; третье лицо, меньший приоритет и так далее. Вас не накажут, если вы не соблюдаете принцип «первым пришел — первым обслужен». Вы решили сначала обслужить своего друга, затем первого человека, а затем второго человека. Это означает, что вы отдали своему другу наивысший приоритет. Если смотреть на сценарий с точки зрения робота, то третья позиция имела наибольший приоритет.

На следующий день пришли те же трое. На этот раз ваш друг находится посередине. Вы решили служить ему первым, впереди того, кто пришел первым, затем третьего лица и, наконец, первого лица. Итак, на этот раз, по мнению робота, позиция 2 имеет наибольший приоритет, за ней следует позиция 3.

На третий день ваш друг становится первым, и вы действуете по принципу «первым пришел — первым обслужен». Вывод любого и робота состоит в том, что приоритет зависит от того, кого это касается, и от позиции каждого человека. Примечание: в реальной жизни приоритет не всегда зависит от принципа «первым пришел — первым обслужен».

В программировании очередь с двоичным приоритетом — это очередь, в которой первый элемент имеет наибольший приоритет. Третий элемент может иметь больший приоритет, а второй элемент — третий приоритет. Очереди приоритетов имеют бинарную природу. Примечание: первый элемент всегда имеет наивысший приоритет в очереди приоритетов. Также может случиться так, что второй элемент имеет больший приоритет, а третий элемент имеет третий приоритет. В определении очереди приоритетов приоритеты второго и третьего элементов могут быть не в порядке убывания. Эта разница продолжается вниз по очереди до последнего элемента, который не может быть элементом с наименьшим приоритетом. Однако он будет одним из наименее приоритетных. Эта частичная сортировка также известна как частичная сортировка. Итак, очередь с приоритетом — это очередь с частичным порядком, где приоритет не «первым пришел — первым обслужен»,

При работе с массивом «первым пришел — первым обслужен» является «первым поступил — первым обслужен», записывается как FIFO. В вычислениях очередь — это FIFO, а очередь с приоритетом — частичная FIFO, потому что по мере убывания очереди некоторые элементы имеют более высокие приоритеты, чем их ближайшие предшественники. По мере дальнейшего опускания очереди приоритетов расстояние между такими ближайшими предшественниками и более высокими приоритетами увеличивается.

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

Структура данных кучи

Есть максимальная куча и есть минимальная куча. С max-heap первый элемент является самым большим значением. По мере спуска очереди значения продолжают уменьшаться, увеличиваться и вообще уменьшаться. В min-heap первый элемент является наименьшим значением. По мере опускания очереди значения продолжают увеличиваться, уменьшаться и в целом увеличиваться. Значения кучи можно хранить в массиве.

Двоичная куча — это место, где узел (элемент) имеет двух дочерних элементов. Первый ребенок — левый ребенок, а второй ребенок — правый ребенок. Значение любого узла называется ключом.

Max-Heap

Следующий список представляет собой максимальную кучу, которая уже частично упорядочена и не нуждается в дальнейшем упорядочении:

89, 85, 87, 84, 82, 79, 73, 80, 81, , , 65, 69

89 — первое значение с индексом 0. Это корневой узел (корневой родитель). Это самая большая ценность среди всех ценностей. Его первый потомок (85) имеет индекс 1, индекс которого равен 2(0) + 1, где 0 — индекс родителя. Его второй потомок (87) имеет индекс 2, что равно 2(0) + 2, где 0 — индекс родителя.

85 находится в индексе 1. Это родитель. Его первый потомок (84) имеет индекс 3, что равно 2(1) + 1, где 1 — индекс родителя. Его второй потомок (82) имеет индекс 4, что равно 2(1) + 2, где 1 — индекс родителя.

87 находится в индексе 2. Это родитель. Его первый потомок (79) имеет индекс 5, что равно 2(2) + 1, где 2 — индекс родителя. Его второй потомок (73) имеет индекс 6, что равно 2(2) + 2, где 2 — индекс родителя.

В общем, поскольку подсчет индексов начинается с 0, пусть i представляет индекс родителя массива; и, таким образом, левый (первый) потомок родителя с индексом i имеет индекс 2i + 1; а его правый (второй) дочерний элемент имеет индекс 2i + 2. Некоторые ячейки ближе к концу массива могут быть пустыми; они не должны иметь значений.

Предыдущий список — хороший пример содержимого приоритетной очереди после завершения включения всех элементов. Если первый элемент удаляется, остальные перестраиваются для установки значений, образуя новую очередь приоритетов. Таким образом, удаление всех элементов сверху будет выглядеть так, как будто все элементы отсортированы правильно. Элементы по-прежнему можно получить как есть, в частичном порядке, без удаления какого-либо элемента.

Min-Heap

Min-heap — это обратная сторона max-heap.

Приоритетная очередь в Java

В Java есть класс PriorityQueue для Priority-Queue. Он имеет множество конструкторов и методов. Ниже описаны только три конструктора и более подходящие методы:

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

Public PriorityQueue()

Это создает приоритетную очередь без какого-либо элемента. Класс PriorityQueue находится в пакете java.util.*, который необходимо импортировать. Следующий сегмент кода создает пустую PriorityQueue, а затем добавляет в очередь несортированные (даже частично не отсортированные) значения:

PriorityQueue<Integer> pq = new PriorityQueue<Integer>();



pq.add(69); pq.add(65); pq.add(87); pq.add(79);



pq.add(73); pq.add(84); pq.add(89); pq.add(80);



pq.add(81); pq.add(82); pq.add(85);

Все эти числа целые. Они взяты из частично отсортированного списка, приведенного выше, но в настоящее время они полностью не отсортированы по мере ввода. Элементы в pq теперь частично отсортированы в соответствии с определением приоритетной очереди в Java.

Public PriorityQueue(PriorityQueue<? extends E> c)

Это создает приоритетную очередь из другой приоритетной очереди. Следующий сегмент кода иллюстрирует это:

PriorityQueue<Integer> pq = new PriorityQueue<Integer>();



pq.add(69); pq.add(65); pq.add(87); pq.add(79);



pq.add(73); pq.add(84); pq.add(89); pq.add(80);



pq.add(81); pq.add(82); pq.add(85);



PriorityQueue<Integer> pq1 = new PriorityQueue<Integer>(pq);

pq1 был создан из pq. В настоящее время он имеет тот же частичный порядок и pq.

Третий метод конструктора показан ниже.

Java-методы приоритетной очереди

Public Int Size()

Это возвращает размер списка и не включает пустые ячейки, как показано в следующем коде:

PriorityQueue<Integer> pq = new PriorityQueue<Integer>();



pq.add(69); pq.add(65); pq.add(87); pq.add(79);



pq.add(73); pq.add(84); pq.add(89); pq.add(80);



pq.add(81); pq.add(82); pq.add(85);



int sz = pq.size();



System.out.println(sz);

Вывод 11.

Public Void forEach(Consumer<? super E> action)

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

PriorityQueue<Integer> pq = new PriorityQueue<Integer>();



pq.add(69); pq.add(65); pq.add(87); pq.add(79);



pq.add(73); pq.add(84); pq.add(89); pq.add(80);



pq.add(81); pq.add(82); pq.add(85);



pq.forEach (item -> System.out.print(item + " "));



System.out.println();

Обратите внимание на то, как сделан код в скобках метода forEach. Элемент — это фиктивная переменная, которая представляет каждый элемент в очереди. Обратите внимание на использование оператора стрелки. Результат:

65 69 84 79 73 87 89 80 81 82 85

Вывод правильный, в частичном порядке, но в порядке возрастания. Это не обязательно обратный порядок, указанный выше, из-за способа включения значений в список. То есть метод forEach возвращает список в виде минимальной кучи. Чтобы вернуть список в порядке убывания, используйте следующий конструктор:

Public PriorityQueue(Comparator<? super E> comparator)

Это конструктор. Следующий код показывает, как его использовать:

PriorityQueue<Integer> pq = new PriorityQueue<Integer>((x, y) -> Integer.compare(y, x));



pq.add(69); pq.add(65); pq.add(87); pq.add(79);



pq.add(73); pq.add(84); pq.add(89); pq.add(80);



pq.add(81); pq.add(82); pq.add(85);



pq.forEach (item -> System.out.print(item + " "));

X, y — фиктивные переменные, представляющие меньшее и меньшее значения. Обратите внимание, что в первых скобках для x и y x стоит перед y. Во вторых скобках y стоит перед x. Результат:

89 85 87 80 82 69 84 65 79 73 81

PriorityQueue<Integer> pq = new PriorityQueue<Integer>((x, y) -> Integer.compare(y, x));



pq.add(69); pq.add(65); pq.add(87); pq.add(79);



pq.add(73); pq.add(84); pq.add(89); pq.add(80);



pq.add(81); pq.add(82); pq.add(85); pq.add(70);



pq.forEach (item -> System.out.print(item + " "));

89 85 87 80 82 70 84 65 79 73 81 69

PriorityQueue<Integer> pq = new PriorityQueue<Integer>((x, y) -> Integer.compare(y, x));



pq.add(69); pq.add(65); pq.add(87); pq.add(79);



pq.add(73); pq.add(84); pq.add(89); pq.add(80);



pq.add(81); pq.add(82); pq.add(85); pq.add(70);



pq.forEach (item -> System.out.print(pq.poll() + " "));

89 87 85 84 82 81 80 79 73 70 69 65 Exception in thread "main" java.util.ConcurrentModificationException



at java.base/java.util.PriorityQueue.forEach(PriorityQueue.java:984)



at TheClass.main(TheClass.java:11)