Вы, должно быть, сталкивались с этими структурами данных - Heap / Queues / Priority Queues. Зачем нам нужны приоритетные очереди, когда у нас есть очереди. А также кучи называются приоритетными очередями, тогда они же? В чем разница между очередями / очередями приоритета и кучей / очередями приоритета? Давайте обсудим это.
Очереди:
Это очень легко понять. Как и очереди в реальности, первая запись в очередь будет удалена первой, то есть FIFO-first In - first Out.
например если ввести эти числа в следующем порядке: 6 → 3 → 8 → 2 в очередь. Затем при извлечении значений из него: порядок их извлечения будет: 6 → 3 → 8 → 2, то есть в том же порядке, что и при вставке. 6 был введен первым, поэтому он будет удален раньше остальных.
Приоритетная очередь:
Как следует из названия, это очередь, но имеет какое-то отношение к приоритету.
При извлечении значений из PQ, запись с наивысшим приоритетом удаляется первой (не следуя порядку FIFO, как в обычных очередях).
Возьмем, к примеру, порядок вставки:
A (P = 4) → B (P = 3) → C (P = 5) → D (p = 9)
Таким образом, при извлечении из PQ порядок удаления будет:
D (p = 9) → C (P = 5) → A (P = 4) → B (P = 3)
В каком-то смысле это не совсем очередь, но я предполагаю, что используется имя Priority Queue, потому что, если более 1 элемента имеют одинаковый приоритет, то их порядок или удаление осуществляется методом FIFO. Так что у него также есть свойства очереди.
Куча:
Куча - это структура данных, лучше всего подходящая для реализации приоритетных очередей. Кучи представлены с использованием массивов (обычно) и могут получить максимальный (или наивысший приоритет) элемент в O (1).
Кучи визуализируются как двоичное дерево с элементами, хранящимися внутри массива, как показано:
Таким образом, элемент с наивысшим приоритетом всегда является корневым, что делает операцию getMax () равной O (1).
