Очередь с приоритетом: различия между версиями
СВ (обсуждение | вклад) |
СВ (обсуждение | вклад) |
||
| Строка 572: | Строка 572: | ||
# Knuth D. E. ''The Art of Computer Programming''. Vol. 3: Sorting and Searching. — Addison-Wesley, 2nd ed., 1998. — §5.2.3. | # Knuth D. E. ''The Art of Computer Programming''. Vol. 3: Sorting and Searching. — Addison-Wesley, 2nd ed., 1998. — §5.2.3. | ||
# Wikipedia: Priority queue. URL: https://en.wikipedia.org/wiki/Priority_queue. | # Wikipedia: Priority queue. URL: https://en.wikipedia.org/wiki/Priority_queue. | ||
[[Category:Алгоритмы и структуры данных]] | |||
Версия 00:25, 9 октября 2026
TL;DR
Очередь с приоритетом (priority queue) — абстрактный тип данных (ADT) над множеством пар «ключ: значение», в котором извлекается элемент с экстремальным ключом (минимумом или максимумом). Интерфейс: Insert, Find-Min, Extract-Min, Decrease-Key, Delete, Merge. Это не одна структура, а спецификация, которую реализуют разные структуры данных: двоичная куча (универсальный выбор), биномиальная и фибоначчиева кучи (быстрые слияние и decrease-key), сбалансированное BST, bucket- и radix-кучи для целых ключей. Типичные оценки: Insert/Extract-Min за [math]\displaystyle{ O(\log n) }[/math], Find-Min за [math]\displaystyle{ O(1) }[/math], а в фибоначчиевой куче Decrease-Key и слияние — амортизированно [math]\displaystyle{ O(1) }[/math]. Очередь с приоритетом лежит в основе Дейкстры и Прима, Хаффмана, слияния [math]\displaystyle{ k }[/math] списков, дискретного моделирования и планировщиков.
| Свойство | Значение |
|---|---|
| Класс | Абстрактный тип данных (ADT); конкретные реализации — кучи, деревья, ведра |
| Основные операции | Insert, Find-Min/Peek, Extract-Min, Decrease-Key/Increase-Key, Delete, Merge
|
| Тип порядка | min-приоритет (минимум первым) либо max-приоритет (максимум первым) |
| Ключ vs значение | Ключ задаёт приоритет; значение — полезная нагрузка элемента |
| Типичная сложность | Find-Min [math]\displaystyle{ O(1) }[/math]; Insert/Extract-Min [math]\displaystyle{ O(\log n) }[/math]; лучшие реализации — Insert [math]\displaystyle{ O(1) }[/math], Decrease-Key аморт. [math]\displaystyle{ O(1) }[/math]
|
| Адресация элемента | Для Decrease-Key/Delete нужен дескриптор (указатель/индекс)
|
| Память | [math]\displaystyle{ O(n) }[/math] для всех основных реализаций |
| Устойчивость | По умолчанию нет; равные ключи разрешаются правилом tie-break |
| Реализации | неупор. массив, сорт. массив/список, двоичная/d-арная/биномиальная/фибоначчиева/pairing-кучи, BST, bucket/radix, van Emde Boas |
| Где встречается | Дейкстра, Прим, Хаффман, k-way merge, top-k, медиана, планировщики ОС, дискретное моделирование, сети |
Определения
Очередь с приоритетом (priority queue) — абстрактный тип данных, хранящий множество элементов, каждому из которых приписан ключ (приоритет) из линейно упорядоченного множества, и поддерживающий извлечение элемента с наименьшим (min-приоритет) или наибольшим (max-приоритет) ключом.
Элемент и ключ. Элемент (значение) — полезная нагрузка; ключ — число, кортеж или иной объект с отношением порядка. Один и тот же ключ может встречаться у нескольких элементов. В очереди обычно допускаются дубликаты ключей, а порядок их выдачи задаётся правилом tie-break.
Дескриптор (handle / descriptor). Ссылка на конкретный элемент внутри очереди (узел, указатель или индекс). Нужен для операций Decrease-Key и Delete, которые адресуют элемент, а не ключ.
Формальный контракт (для min-приоритетной очереди [math]\displaystyle{ Q }[/math] над множеством [math]\displaystyle{ S }[/math] пар [math]\displaystyle{ (k, v) }[/math]):
| Операция | Предусловие | Постусловие |
|---|---|---|
Insert(Q, k, v) |
— | [math]\displaystyle{ S' = S \cup \{(k,v)\} }[/math] |
Min(Q) / Peek(Q) |
[math]\displaystyle{ S \ne \varnothing }[/math] | возвращён [math]\displaystyle{ v }[/math] с ключом [math]\displaystyle{ k = \min\{k_i\} }[/math] |
Extract-Min(Q) |
[math]\displaystyle{ S \ne \varnothing }[/math] | возвращён и удалён минимум |
Decrease-Key(Q, x, k′) |
[math]\displaystyle{ x \in S }[/math], [math]\displaystyle{ k' \le k_x }[/math] | ключ [math]\displaystyle{ x }[/math] стал [math]\displaystyle{ k' }[/math] |
Increase-Key(Q, x, k′) |
[math]\displaystyle{ x \in S }[/math], [math]\displaystyle{ k' \ge k_x }[/math] | ключ [math]\displaystyle{ x }[/math] стал [math]\displaystyle{ k' }[/math] |
Delete(Q, x) |
[math]\displaystyle{ x \in S }[/math] | [math]\displaystyle{ S' = S \setminus \{x\} }[/math] |
Merge(Q₁, Q₂) |
— | очередь [math]\displaystyle{ S_1 \cup S_2 }[/math] |
Build(S) |
— | очередь из всех элементов [math]\displaystyle{ S }[/math] |
ADT против структуры данных. Очередь с приоритетом — это спецификация (что делают операции); конкретные структуры (кучи, деревья, ведра) — реализации (как они это делают). Одна и та же ADT имеет много реализаций с разным балансом стоимостей.
Обозначения. [math]\displaystyle{ n }[/math] — число элементов; [math]\displaystyle{ m }[/math] — число операций (в применениях — рёбер графа); [math]\displaystyle{ C }[/math] — верхняя граница целочисленного ключа; [math]\displaystyle{ U }[/math] — размер вселенной ключей; [math]\displaystyle{ \log }[/math] — по основанию 2.
Extract-Min всегда возвращает элемент с наименьшим ключом.Мотивация и интуиция
Многие алгоритмы многократно задают один и тот же вопрос: «кто сейчас самый приоритетный?». Планировщик ищет ближайшую по времени задачу, Дейкстра — ближайшую непомеченную вершину, кодер Хаффмана — два самых редких символа. Прямолинейное решение — хранить элементы в массиве и каждый раз искать минимум линейным просмотром — стоит [math]\displaystyle{ O(n) }[/math] на запрос; поддерживать полный порядок (отсортированный массив) — [math]\displaystyle{ O(n) }[/math] на вставку. При больших [math]\displaystyle{ n }[/math] и частых запросах оба варианта плохи.
Ключевое наблюдение: нужен не полный порядок, а только экстремум. Очередь с приоритетом хранит данные так, что экстремум доступен быстро, а порядок между «неинтересными» элементами не поддерживается вовсе. Это позволяет сделать одну операцию за [math]\displaystyle{ O(1) }[/math], а остальные — за [math]\displaystyle{ O(\log n) }[/math], не тратя время на сортировку всего множества.
Ещё одна идея — отложенная работа. Операции, которые дешево выполнить сразу, выполняются сразу (Insert за [math]\displaystyle{ O(1) }[/math] в фибоначчиевой куче), а наведение порядка откладывается до Extract-Min (консолидация). Амортизационный анализ показывает, что в среднем всё дёшево.
Устройство
Очередь с приоритетом реализуют, выбирая структуру под требуемый набор операций и модель ключей. Два главных вопроса:
- Какие операции критичны? Нужен ли быстрый
Decrease-Key? Частое слияние? Гарантия худшего случая или достаточно амортизированной? Порядковая статистика (successor/predecessor)? - Какие ключи? Сравнимые (любой порядок) или целые из малого диапазона? Есть ли границы?
Дескрипторы и адресация. Для Decrease-Key/Delete структура должна уметь находить элемент по дескриптору. Двоичная куча добавляет к массиву карту позиций pos[id] (индексированная куча); кучи на узлах хранят указатель узла; при ленивом подходе дескрипторов вообще нет, а устаревшие записи отбрасываются при извлечении.
Модель ключей.
- Сравнительная: ключи только сравниваются; нижняя граница [math]\displaystyle{ \Omega(\log n) }[/math] на извлечение для достаточно богатого набора операций.
- Целочисленная ограниченная: ключи из [math]\displaystyle{ \{0, \dots, C\} }[/math] позволяют bucket- и radix-кучи с [math]\displaystyle{ O(1) }[/math] амортизированно на операцию при малом диапазоне.
Операции и алгоритмы
Ниже операции заданы на уровне ADT (контракт и инварианты), а конкретные стоимости приведены для канонических реализаций. Подробные алгоритмы кучи — в статьях Двоичная куча, Биномиальная куча, Фибоначчиева куча.
Операция: вставка (Insert)
Идея. Добавить пару [math]\displaystyle{ (k, v) }[/math] в структуру так, чтобы контракт остался выполнен.
Контракт и инвариант. После операции множество содержит новый элемент; порядок остальных не меняется; инварианты конкретной структуры (например, свойство кучи) восстановлены.
Псевдокод (в терминах двоичной кучи).
Алгоритм PriorityQueue-Insert(Q, k, v)
Вход: Q — min-очередь; (k, v) — новый элемент
Выход: Q содержит (k, v)
1 добавить новый узел x со ключом k в конец массива-кучи
2 pos[x] ← индекс x # для доступа по дескриптору
3 sift-up(x) # поднять, пока key[parent] > key[x]
4 size[Q] ← size[Q] + 1
Сложность: двоичная куча O(log n); d-арная O(log_d n); биномиальная аморт. O(1); фибоначчиева O(1). Память O(1). Корректность: свойство кучи восстанавливается подъёмом; остальные узлы не затронуты.
Крайние случаи. Вставка в пустую очередь — новый элемент становится корнем. Вставка ключа, меньшего текущего минимума, в куче завершается сразу.
Операция: чтение минимума (Find-Min / Peek)
Контракт. Возвращает ссылку на элемент с наименьшим ключом, не удаляя его; ошибка, если очередь пуста. В кучах минимум доступен напрямую (корень или указатель min) — [math]\displaystyle{ O(1) }[/math]; в неупорядоченном массиве — [math]\displaystyle{ O(n) }[/math].
Алгоритм PriorityQueue-Min(Q)
Вход: Q — непустая min-очередь
Выход: элемент с наименьшим ключом
1 return элемент, на который указывает минимум структуры
Сложность: O(1) для всех куч (и O(1) при хранении указателя даже там, где он неявный).
Операция: извлечение минимума (Extract-Min)
Идея. Вернуть и удалить минимум, восстановив инвариант структуры.
Контракт и инвариант. Возвращённый элемент имел минимальный ключ; после удаления структура корректна.
Псевдокод (в терминах двоичной кучи).
Алгоритм PriorityQueue-Extract-Min(Q)
Вход: Q — непустая min-очередь
Выход: элемент с наименьшим ключом; он удалён
1 min ← корень кучи
2 переместить последний элемент кучи в корень; size[Q] ← size[Q] − 1
3 sift-down(корень) # опустить, пока key > key[старшего ребёнка]
4 pos[min] ← −1
5 return min
Сложность: двоичная куча O(log n); d-арная O(d·log_d n); биномиальная O(log n); фибоначчиева аморт. O(log n). Память O(1).
Корректность: после удаления оба поддерева корня — кучи, поэтому sift-down восстанавливает свойство кучи во всём дереве.
Крайние случаи. Последний элемент — очередь пустеет. Единственный ребёнок (при чётном [math]\displaystyle{ n }[/math]) — сравнение только с ним.
Операция: изменение ключа (Decrease-Key / Increase-Key)
Идея. Уменьшить (для min-очереди) ключ элемента: он может «подняться» к корню. Нужен дескриптор элемента. В структурах без decrease-key применяют ленивое удаление (рис. 3).
Контракт и инвариант. Новый ключ не больше старого; инвариант кучи восстановлен подъёмом.
Псевдокод (индексированная куча).
Алгоритм Indexed-Decrease-Key(Q, id, k′)
Вход: id — дескриптор; k′ ≤ key[id]
Выход: ключ элемента уменьшен
1 key[id] ← k′
2 i ← pos[id] # O(1) благодаря карте позиций
3 sift-up(i) # при обмене обновляются pos для обоих узлов
Сложность: O(log n) (высота кучи); в фибоначчиевой куче — амортизированно O(1). Корректность: подъём останавливается, когда ключ не меньше ключа родителя, что и есть свойство min-кучи.
Ленивый вариант (когда decrease-key нет) — рис. 3:
Алгоритм Lazy-Extract-Min(Q, dist)
Вход: Q — очередь с возможными устаревшими записями; dist[v] — актуальные ключи
Выход: элемент с наименьшим актуальным ключом
1 repeat
2 (k, v) ← Extract-Min(Q)
3 if k = dist[v] # запись актуальна
4 return (k, v)
5 # иначе запись устарела — просто пропускаем и берём следующую
Сложность: амортизированно O(log n) на актуальное извлечение; каждая релаксация кладёт не более одной лишней записи, поэтому суммарное число записей O(m).
Крайние случаи. Уменьшение ключа текущего минимума сохраняет его минимумом. Попытка уменьшить несуществующий элемент (неверный дескриптор) — ошибка.
decrease-key) или класть дубликат и пропускать устаревшие записи при извлечении (ленивый вариант).
pos[id] — позицию элемента в массиве-куче. Это даёт доступ к элементу за [math]\displaystyle{ O(1) }[/math] и делает Decrease-Key выполнимым за [math]\displaystyle{ O(\log n) }[/math].Операция: удаление элемента (Delete)
Идея. Удалить конкретный элемент по дескриптору. Универсальный приём: уменьшить ключ до [math]\displaystyle{ -\infty }[/math] и извлечь минимум.
Алгоритм PriorityQueue-Delete(Q, x)
Вход: x — дескриптор элемента
Выход: элемент удалён
1 Decrease-Key(Q, x, −∞)
2 Extract-Min(Q) # удаляемый элемент теперь минимум
Сложность: O(log n) для куч (в фибоначчиевой амортизированно O(log n)).
Корректность: после Decrease-Key x — минимум, поэтому Extract-Min удаляет именно его.
Крайний случай. Если у элемента есть операция прямого удаления по позиции (индексированная куча), удаляют заменой на последний и просеиванием в нужную сторону — без «[math]\displaystyle{ -\infty }[/math]».
Операция: слияние (Merge / Meld)
Идея. Объединить две очереди в одну. Стоимость решающим образом зависит от реализации: копирование массива ([math]\displaystyle{ \Theta(n) }[/math]), сцепка списков корней ([math]\displaystyle{ O(1) }[/math]), слияние лесов ([math]\displaystyle{ O(\log n) }[/math]).
Алгоритм PriorityQueue-Merge(Q1, Q2)
Вход: Q1, Q2 — очереди
Выход: очередь со всеми элементами Q1 и Q2
1 if структура meldable # биномиальная, фибоначчиева, pairing
2 сцепить / слить внутренние структуры за O(1) или O(log n)
3 else # двоичная куча на массиве
4 перенести все элементы Q2 в Q1 (перестроение кучи — Θ(n))
Сложность: двоичная куча Θ(n); биномиальная O(log n); фибоначчиева O(1).
Крайние случаи. Слияние с пустой очередью — возврат второй как есть.
Bucket-очередь для целых ключей из [math]\displaystyle{ [0, C] }[/math] (рис. 5): Insert/Decrease-Key за [math]\displaystyle{ O(1) }[/math], Extract-Min продвигает указатель по ведрам; суммарно [math]\displaystyle{ O(C + n) }[/math]. Применяется, когда диапазон ключей мал (например, малые веса рёбер в алгоритме Дейкстры — «алгоритм Диала»).
Операция: построение (Build)
Идея. Построить очередь из готового набора за [math]\displaystyle{ O(n) }[/math], если структура это позволяет (двоичная куча — Build-Heap за [math]\displaystyle{ O(n) }[/math]; биномиальная/фибоначчиева — [math]\displaystyle{ n }[/math] вставок амортизированно [math]\displaystyle{ O(n) }[/math]). Наивные [math]\displaystyle{ n }[/math] вставок в двоичную кучу дали бы [math]\displaystyle{ O(n\log n) }[/math].
Реализация на C++
Полноценный ADT лучше всего показать на индексированной двоичной куче (min-приоритет): она поддерживает Insert, Find-Min, Extract-Min, Decrease-Key/Increase-Key и Delete по дескриптору-идентификатору. Компаратор по умолчанию std::less даёт min-кучу.
#include <iostream>
#include <vector>
#include <cassert>
#include <functional>
template <typename K, typename V, typename Compare = std::less<K>>
class IndexedPriorityQueue {
std::vector<K> key_;
std::vector<V> val_;
std::vector<int> pos_; // pos_[id] — позиция в heap_ или -1
std::vector<int> heap_; // heap_[i] — id элемента
Compare comp_; // comp_(a, b): a имеет более высокий приоритет
std::size_t size_ = 0;
bool active(int id) const { return pos_[id] != -1; }
bool higher(int a, int b) const { return comp_(key_[a], key_[b]); }
static int parent(int i) { return (i - 1) / 2; }
void swapIds(int i, int j) {
std::swap(heap_[i], heap_[j]);
pos_[heap_[i]] = i;
pos_[heap_[j]] = j;
}
void siftUp(int i) {
while (i > 0) {
int p = parent(i);
if (!higher(heap_[i], heap_[p])) break;
swapIds(i, p);
i = p;
}
}
void siftDown(int i) {
while (true) {
int l = 2 * i + 1, r = 2 * i + 2, best = i;
if (l < static_cast<int>(heap_.size()) && higher(heap_[l], heap_[best])) best = l;
if (r < static_cast<int>(heap_.size()) && higher(heap_[r], heap_[best])) best = r;
if (best == i) break;
swapIds(i, best);
i = best;
}
}
public:
explicit IndexedPriorityQueue(std::size_t capacity) {
key_.resize(capacity);
val_.resize(capacity);
pos_.assign(capacity, -1);
}
void insert(int id, const K& k, const V& v) {
assert(id >= 0 && id < static_cast<int>(pos_.size()));
assert(!active(id));
key_[id] = k;
val_[id] = v;
heap_.push_back(id);
pos_[id] = static_cast<int>(heap_.size()) - 1;
++size_;
siftUp(pos_[id]);
}
bool contains(int id) const { return active(id); }
std::size_t size() const { return size_; }
bool empty() const { return size_ == 0; }
int minId() const { assert(!empty()); return heap_.front(); }
const K& minKey() const { assert(!empty()); return key_[heap_.front()]; }
const V& minValue() const { assert(!empty()); return val_[heap_.front()]; }
int extractMin() {
assert(!empty());
int id = heap_.front();
int last = heap_.back();
heap_.pop_back();
pos_[id] = -1;
--size_;
if (!heap_.empty()) {
heap_.front() = last;
pos_[last] = 0;
siftDown(0);
}
return id;
}
void changeKey(int id, const K& newKey) { // Decrease- или Increase-Key
assert(active(id));
bool increased = comp_(key_[id], newKey); // newKey больше
key_[id] = newKey;
if (increased) siftDown(pos_[id]);
else siftUp(pos_[id]);
}
void decreaseKey(int id, const K& newKey) {
assert(active(id) && !comp_(key_[id], newKey)); // newKey <= текущего
key_[id] = newKey;
siftUp(pos_[id]);
}
void erase(int id) { // Delete по дескриптору
assert(active(id));
int i = pos_[id];
int last = heap_.back();
heap_.pop_back();
pos_[id] = -1;
--size_;
if (i < static_cast<int>(heap_.size())) {
heap_[i] = last;
pos_[last] = i;
if (i > 0 && higher(last, heap_[parent(i)])) siftUp(i);
else siftDown(i);
}
}
bool validate() const {
for (std::size_t i = 0; i < heap_.size(); ++i) {
if (pos_[heap_[i]] != static_cast<int>(i)) return false;
if (i > 0 && higher(heap_[i], heap_[parent(i)])) return false;
}
std::size_t active = 0;
for (int p : pos_) if (p != -1) ++active;
return active == size_ && heap_.size() == size_;
}
};
int main() {
IndexedPriorityQueue<int, int> q(5);
q.insert(0, 7, 100);
q.insert(1, 3, 101);
q.insert(2, 9, 102);
q.insert(3, 1, 103);
assert(q.validate());
assert(q.minId() == 3 && q.minKey() == 1);
q.decreaseKey(2, 0); // 9 → 0: теперь минимум
assert(q.validate());
assert(q.minId() == 2 && q.minKey() == 0);
q.changeKey(1, 5); // 3 → 5: увеличение
assert(q.validate());
std::vector<int> ids;
while (!q.empty()) ids.push_back(q.extractMin());
assert((ids == std::vector<int>{2, 3, 1, 0})); // ключи 0, 1, 5, 7
assert(q.validate());
// Dijkstra-подобный сценарий: обновляем ключи соседей
IndexedPriorityQueue<long long, int> d(4);
for (int v = 0; v < 4; ++v) d.insert(v, 1000000000LL, v);
d.decreaseKey(0, 0);
d.decreaseKey(1, 5);
d.decreaseKey(1, 2); // повторное улучшение
assert(d.minKey() == 0);
d.extractMin();
assert(d.minKey() == 2 && d.minId() == 1);
std::cout << "ok\n";
return 0;
}
Стандартная библиотека. В C++ std::priority_queue<T> — это max-куча; std::priority_queue<T, std::vector<T>, std::greater<T>> — min-куча. Она не поддерживает decrease-key и адресацию элементов, поэтому для Дейкстры либо применяют ленивое удаление, либо пишут индексированную кучу, как выше.
Сводная таблица сложности
Стоимости в худшем/амортизированном случае для [math]\displaystyle{ n }[/math] элементов ([math]\displaystyle{ \log }[/math] — двоичный).
| Реализация | Insert | Find-Min | Extract-Min | Decrease-Key | Merge | Build | Память |
|---|---|---|---|---|---|---|---|
| Неупор. массив | [math]\displaystyle{ O(1) }[/math] | [math]\displaystyle{ O(n) }[/math] | [math]\displaystyle{ O(n) }[/math] | [math]\displaystyle{ O(1) }[/math] | [math]\displaystyle{ O(n) }[/math] | [math]\displaystyle{ O(n) }[/math] | [math]\displaystyle{ O(n) }[/math] |
| Сорт. массив | [math]\displaystyle{ O(n) }[/math] | [math]\displaystyle{ O(1) }[/math] | [math]\displaystyle{ O(1) }[/math] | [math]\displaystyle{ O(n) }[/math] | [math]\displaystyle{ O(n) }[/math] | [math]\displaystyle{ O(n\log n) }[/math] | [math]\displaystyle{ O(n) }[/math] |
| Двоичная куча | [math]\displaystyle{ O(\log n) }[/math] | [math]\displaystyle{ O(1) }[/math] | [math]\displaystyle{ O(\log n) }[/math] | [math]\displaystyle{ O(\log n) }[/math] | [math]\displaystyle{ \Theta(n) }[/math] | [math]\displaystyle{ O(n) }[/math] | [math]\displaystyle{ O(n) }[/math] |
| d-арная куча | [math]\displaystyle{ O(\log_d n) }[/math] | [math]\displaystyle{ O(1) }[/math] | [math]\displaystyle{ O(d\log_d n) }[/math] | [math]\displaystyle{ O(\log_d n) }[/math] | [math]\displaystyle{ \Theta(n) }[/math] | [math]\displaystyle{ O(n) }[/math] | [math]\displaystyle{ O(n) }[/math] |
| Биномиальная куча | аморт. [math]\displaystyle{ O(1) }[/math] | [math]\displaystyle{ O(\log n) }[/math] | [math]\displaystyle{ O(\log n) }[/math] | [math]\displaystyle{ O(\log n) }[/math] | [math]\displaystyle{ O(\log n) }[/math] | [math]\displaystyle{ O(n) }[/math] | [math]\displaystyle{ O(n) }[/math] |
| Фибоначчиева куча | [math]\displaystyle{ O(1) }[/math] | [math]\displaystyle{ O(1) }[/math] | аморт. [math]\displaystyle{ O(\log n) }[/math] | аморт. [math]\displaystyle{ O(1) }[/math] | [math]\displaystyle{ O(1) }[/math] | [math]\displaystyle{ O(n) }[/math] | [math]\displaystyle{ O(n) }[/math] |
| Pairing-куча | [math]\displaystyle{ O(1) }[/math] | [math]\displaystyle{ O(1) }[/math] | аморт. [math]\displaystyle{ O(\log n) }[/math] | аморт. [math]\displaystyle{ O(\log n) }[/math] | [math]\displaystyle{ O(1) }[/math] | [math]\displaystyle{ O(n) }[/math] | [math]\displaystyle{ O(n) }[/math] |
| Сбалансированное BST | [math]\displaystyle{ O(\log n) }[/math] | [math]\displaystyle{ O(\log n) }[/math] | [math]\displaystyle{ O(\log n) }[/math] | [math]\displaystyle{ O(\log n) }[/math] | [math]\displaystyle{ O(n) }[/math] | [math]\displaystyle{ O(n\log n) }[/math] | [math]\displaystyle{ O(n) }[/math] |
| Bucket queue (ключи [math]\displaystyle{ [0,C] }[/math]) | [math]\displaystyle{ O(1) }[/math] | [math]\displaystyle{ O(C) }[/math] | [math]\displaystyle{ O(1) }[/math] аморт. | [math]\displaystyle{ O(1) }[/math] | [math]\displaystyle{ O(C) }[/math] | [math]\displaystyle{ O(C+n) }[/math] | [math]\displaystyle{ O(C+n) }[/math] |
Примечание. «Лучшая» реализация зависит от нагрузки. Для универсального случая это двоичная куча; при частом decrease-key и слиянии — фибоначчиева (теоретически) или pairing-куча (проще); при целых ключах малого диапазона — bucket/radix. Сбалансированное BST выбирают, когда нужны ещё и successor/predecessor и диапазонные запросы.
Трассировка примера
Последовательность операций над min-очередью (ключи — целые; значения — буквы). Содержимое записано по возрастанию ключа.
| Шаг | Операция | Результат | Содержимое Q |
|---|---|---|---|
| 1 | Insert(з, 5) |
— | з:5 |
| 2 | Insert(б, 3) |
— | б:3, з:5 |
| 3 | Insert(в, 8) |
— | б:3, з:5, в:8 |
| 4 | Decrease-Key(в, 1) |
— | в:1, б:3, з:5 |
| 5 | Extract-Min |
в:1 | б:3, з:5 |
| 6 | Insert(а, 0) |
— | а:0, б:3, з:5 |
| 7 | Extract-Min |
а:0 | б:3, з:5 |
| 8 | Extract-Min |
б:3 | з:5 |
| 9 | Find-Min |
з:5 | з:5 |
| 10 | Delete(з) |
— | пусто |
Проверки: Find-Min не меняет содержимое; Decrease-Key только улучшает (уменьшает) ключ; сумма извлечённых значений (в:1, а:0, б:3) идёт по неубыванию ключей — контракт соблюдён.
Корректность и оценка сложности
Extract-Min элемент с минимальным ключом и сохраняет множество остальных элементов, то она удовлетворяет контракту ADT.Extract-Min по определению возвращает минимум и удаляет ровно его; повторяя, получаем все постусловия для остальных операций (они затрагивают лишь множество и ключ одного элемента).
Инвариант конкретной реализации. Для двоичной кучи инвариант — «свойство кучи: ключ родителя не больше ключей детей». Из него следует, что корень — минимум: любой другой ключ лежит в поддереве некоторого ребёнка и потому не меньше корня по транзитивности. Это и есть уточнение (refinement) спецификации реализацией: инвариант структуры влечёт постусловие ADT.
Согласованность компаратора. Компаратор должен задавать строгое слабое упорядочение (транзитивность, антисимметричность, согласованность эквивалентности); иначе стандартные контейнеры C++ дают неопределённое поведение, а структура может нарушить порядок.
Устойчивость (stability). Очередь с приоритетом не обязана быть устойчивой. Для FIFO-порядка среди равных ключей используют составной ключ [math]\displaystyle{ (k, \text{seq}) }[/math], где [math]\displaystyle{ \text{seq} }[/math] — монотонно растущий счётчик вставок; сравнение лексикографическое.
Амортизированные границы. В фибоначчиевой куче Decrease-Key амортизированно [math]\displaystyle{ O(1) }[/math], но отдельная операция может дать каскад из [math]\displaystyle{ O(\log n) }[/math] разрезов. Амортизация корректна для любой последовательности операций, но не даёт гарантии на одну операцию — это важно в системах реального времени.
Рандомизация. Для сравнимых ключей нижняя граница [math]\displaystyle{ \Omega(\log n) }[/math] на извлечение (при достаточно богатом наборе операций) не обходится детерминированно; рандомизированные структуры (например, treap) дают те же оценки в ожидании.
Сравнение с альтернативами
| Критерий | Двоичная куча | Биномиальная/Фибоначчиева | Сбалансированное BST | Bucket/Radix |
|---|---|---|---|---|
| Универсальность | высокая | средняя | высокая | только целые ключи |
decrease-key |
[math]\displaystyle{ O(\log n) }[/math] | [math]\displaystyle{ O(\log n) }[/math] / аморт. [math]\displaystyle{ O(1) }[/math] | [math]\displaystyle{ O(\log n) }[/math] | [math]\displaystyle{ O(1) }[/math] |
| Слияние | [math]\displaystyle{ \Theta(n) }[/math] | [math]\displaystyle{ O(\log n) }[/math] / [math]\displaystyle{ O(1) }[/math] | [math]\displaystyle{ O(n) }[/math] | [math]\displaystyle{ O(C) }[/math] |
| Порядковые запросы | нет | нет | successor/predecessor |
нет |
| Константы/память | низкие | высокие | высокие | очень низкие |
| Когда выбирать | общий случай | частые decrease-key/слияния |
нужны порядковые запросы | малые целые ключи |
Вердикт. Начните с двоичной кучи. Если профиль показывает, что доминируют decrease-key или слияния — перейдите к pairing- или фибоначчиевой куче. Если нужны successor/predecessor, диапазонные запросы или упорядоченный обход — берите сбалансированное BST. Если ключи — целые из малого диапазона — bucket/radix-куча даст лучшие константы.
Где применяется
- Коды Хаффмана. На каждом шаге берутся два символа с наименьшими частотами — два
Extract-Minи однаInsert; сжатие за [math]\displaystyle{ O(n\log n) }[/math]. - Слияние [math]\displaystyle{ k }[/math] отсортированных списков (k-way merge). Мини-куча из голов каждого списка выдаёт очередной элемент за [math]\displaystyle{ O(\log k) }[/math]; так работает внешняя сортировка.
- Дискретно-событийное моделирование. Очередь событий упорядочена по времени срабатывания;
Extract-Minберёт ближайшее событие,Insertдобавляет новые. Для больших систем применяют calendar queue. - Планировщики ОС и сетей. Планирование задач по приоритету, weighted fair queuing и QoS выбирают очередной пакет/задачу по приоритету; здесь важна предсказуемость и борьба с «инверсией приоритетов».
- Потоковые top-k, медиана и поиск в ширину по стоимости. Для «[math]\displaystyle{ k }[/math] наибольших в потоке» держат min-кучу размера [math]\displaystyle{ k }[/math]; для медианы — две кучи; в A*/best-first search приоритет — эвристическая оценка.
- Ветви и границы (branch and bound). Очередь хранит подзадачи по нижней оценке;
Extract-Minобрабатывает наиболее перспективную. - Алгоритм Дейкстры и Прим (рис. 7). Очередь хранит вершины по текущей оценке расстояния;
Extract-Minдаёт ближайшую непомеченную вершину,Decrease-Key— обновление оценки. На двоичной куче Дейкстра работает за [math]\displaystyle{ O((n+m)\log n) }[/math], на фибоначчиевой — за [math]\displaystyle{ O(m + n\log n) }[/math].
Extract-Min достаёт ближайшую вершину, Decrease-Key обновляет оценки её соседей; сложность зависит от выбора очереди.Историческая справка
- 1964. Дж. У. Дж. Уильямс предложил двоичную кучу и heapsort [1]; в том же году Р. У. Флойд показал линейное построение кучи [2].
- 1969. Р. Диал предложил bucket-очередь для Дейкстры с малыми целочисленными весами [3].
- 1975–1977. П. ван Эмде Боас разработал структуру с операциями за [math]\displaystyle{ O(\log\log U) }[/math] на вселенной размера [math]\displaystyle{ U }[/math] [4].
- 1978. Ж. Вюйемен ввёл биномиальные кучи с быстрым слиянием [5].
- 1984–1987. М. Фредман и Р. Тарджан предложили фибоначчиевы кучи с амортизированным [math]\displaystyle{ O(1) }[/math] на
decrease-key[6]. - 1986. Фредман, Седжвик, Слейтор и Тарджан предложили pairing-кучи — проще фибоначчиевых [7].
- 2000. Б. Шазель построил soft heap — приближённую очередь с [math]\displaystyle{ O(1) }[/math] амортизированно на операцию и управляемой долей ошибок [8].
Типичные ошибки и подводные камни
- Ожидание
decrease-keyв стандартных контейнерах. Уstd::priority_queueиheapqего нет; нужны ленивое удаление или индексированная куча. - Ленивое удаление без проверки устаревших записей. Если при извлечении не сравнивать ключ записи с текущим, можно вернуть устаревшее значение.
- Неограниченный рост памяти при ленивом удалении. Каждая релаксация добавляет запись; для плотных графов это до [math]\displaystyle{ m }[/math] лишних записей.
- Несогласованный компаратор. Нетранзитивное или нестрогое сравнение ломает инвариант и даёт неопределённое поведение в STL.
- Инверсия приоритетов. Задача с низким приоритетом удерживает ресурс, нужный задаче с высоким; лечится наследованием приоритета.
- Ожидание устойчивости. Равные ключи выдаются в произвольном порядке; для FIFO нужен составной ключ.
- Изменение ключа «на месте». Прямая запись нового ключа в узел кучи без
sift/decrease-keyнарушает инвариант и даёт неверные извлечения. - Переполнение при вычислении ключа.
dist[u] + wна 32-битном типе переполняется; используйте 64-бит или насыщающую арифметику. - Копирование очереди для слияния. Для array-кучи
Mergeстоит [math]\displaystyle{ \Theta(n) }[/math]; не стоит ожидать [math]\displaystyle{ O(1) }[/math]. - Смешение min- и max-приоритета. Двоичная куча STL по умолчанию max; забытый
std::greaterпереворачивает порядок.
Задачи для практики
- Интерфейс vs реализация. Определите ADT-контракт очереди с приоритетом и докажите, что двоичная куча ему удовлетворяет. Подсказка: свойство кучи влечёт минимум в корне.
- Индексированная куча. Реализуйте
Decrease-Keyчерез картуpos[id]; проверьте, чтоposобновляется при каждом обмене. Ограничения: [math]\displaystyle{ n \le 10^6 }[/math]. - Устойчивая очередь. Добавьте счётчик вставок к ключу и получите FIFO-порядок среди равных ключей. Подсказка: сравнивайте пары [math]\displaystyle{ (k, \text{seq}) }[/math] лексикографически.
- Ленивая Дейкстра. Реализуйте Дейкстру со
std::priority_queueи пропуском устаревших записей; сравните с индексированной кучей. Подсказка: храните пару [math]\displaystyle{ (\text{dist}, v) }[/math] и сверяйтеdist[v]. - k-way merge. Слейте [math]\displaystyle{ k }[/math] списков за [math]\displaystyle{ O(N\log k) }[/math]. Подсказка: min-куча из голов списков.
- Top-k в потоке. Держите [math]\displaystyle{ k }[/math] наибольших за [math]\displaystyle{ O(\log k) }[/math] на элемент. Подсказка: min-куча размера [math]\displaystyle{ k }[/math].
- Bucket queue. Реализуйте Диала для графа с малыми целыми весами. Подсказка: массив вёдер по расстояниям, указатель на текущий минимум.
- Выбор структуры. Для трёх сценариев (частый
decrease-key; частые слияния; целые ключи [math]\displaystyle{ [0, 10^4] }[/math]) выберите реализацию и обоснуйте. Подсказка: см. таблицу §8.
Связанные темы
- Двоичная куча — универсальная реализация.
- Биномиальная куча — быстрое слияние.
- Фибоначчиева куча — амортизированное [math]\displaystyle{ O(1) }[/math] на
decrease-key. - Алгоритм дейкстры (план) — основной потребитель
decrease-key. - Алгоритм Прима — минимальное остовное дерево.
- Код хаффмана (план) — жадное сжатие на куче.
- Красно-чёрное дерево и АВЛ-дерево — если нужны порядковые запросы.
- Асимптотическая сложность (план) — нотация [math]\displaystyle{ O }[/math], [math]\displaystyle{ \Omega }[/math], [math]\displaystyle{ \Theta }[/math].
Источники
- ↑ Williams J. W. J. Algorithm 232: Heapsort // Communications of the ACM. — 1964. — Vol. 7, No. 6. — P. 347–348.
- ↑ Cormen T. H., Leiserson C. E., Rivest R. L., Stein C. Introduction to Algorithms (CLRS). 3rd ed. — MIT Press, 2009. — Гл. 6 «Heapsort» (очередь с приоритетом), гл. 19 «Fibonacci Heaps».
- ↑ Dial R. B. Algorithm 360: Shortest-Path Forest with Topological Ordering // Communications of the ACM. — 1969. — Vol. 12, No. 11. — P. 632–633.
- ↑ van Emde Boas P. Preserving Order in a Forest in Less Than Logarithmic Time and Linear Space // Information Processing Letters. — 1977. — Vol. 6, No. 3. — P. 80–82.
- ↑ Vuillemin J. A Data Structure for Manipulating Priority Queues // Communications of the ACM. — Vol. 21, No. 4. — P. 309–315.
- ↑ Fredman M. L., Tarjan R. E. Fibonacci Heaps and Their Uses in Improved Network Optimization Algorithms // Journal of the ACM. — 1987. — Vol. 34, No. 3. — P. 596–615.
- ↑ Fredman M. L., Sedgewick R., Sleator D. D., Tarjan R. E. The Pairing Heap: A New Form of Self-Adjusting Heap // Algorithmica. — 1986. — Vol. 1, No. 1. — P. 111–129.
- ↑ Chazelle B. The Soft Heap: An Approximate Priority Queue with Optimal Error Rate // Journal of the ACM. — 2000. — Vol. 47, No. 6. — P. 1012–1027.
Дополнительные источники
- Knuth D. E. The Art of Computer Programming. Vol. 3: Sorting and Searching. — Addison-Wesley, 2nd ed., 1998. — §5.2.3.
- Wikipedia: Priority queue. URL: https://en.wikipedia.org/wiki/Priority_queue.