Очередь с приоритетом

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.

Рис. 1. Интерфейс очереди с приоритетом и её контракт. Внутри хранятся пары «ключ: значение»; 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 (консолидация). Амортизационный анализ показывает, что в среднем всё дёшево.

Устройство

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

1. Какие операции критичны? Нужен ли быстрый Decrease-Key? Частое слияние? Гарантия худшего случая или достаточно амортизированной? Порядковая статистика (successor/predecessor)?
2. Какие ключи? Сравнимые (любой порядок) или целые из малого диапазона? Есть ли границы?

Дескрипторы и адресация. Для Decrease-Key/Delete структура должна уметь находить элемент по дескриптору. Двоичная куча добавляет к массиву карту позиций pos[id] (индексированная куча); кучи на узлах хранят указатель узла; при ленивом подходе дескрипторов вообще нет, а устаревшие записи отбрасываются при извлечении.

Модель ключей.

• Сравнительная: ключи только сравниваются; нижняя граница [math]\displaystyle{ \Omega(\log n) }[/math] на извлечение для достаточно богатого набора операций.
• Целочисленная ограниченная: ключи из [math]\displaystyle{ \{0, \dots, C\} }[/math] позволяют bucket- и radix-кучи с [math]\displaystyle{ O(1) }[/math] амортизированно на операцию при малом диапазоне.

Рис. 2. Один интерфейс — много реализаций: от простых массивов до фибоначчиевой кучи. Чем больше возможностей, тем выше сложность и константы.

Операции и алгоритмы

Ниже операции заданы на уровне 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).

Крайние случаи. Уменьшение ключа текущего минимума сохраняет его минимумом. Попытка уменьшить несуществующий элемент (неверный дескриптор) — ошибка.

Рис. 3. Два способа обновить приоритет: править ключ на месте (вариант decrease-key) или класть дубликат и пропускать устаревшие записи при извлечении (ленивый вариант).

Рис. 4. Индексированная куча хранит карту 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)

Рис. 5. Bucket queue: элемент с ключом [math]\displaystyle{ k }[/math] кладётся в ведро [math]\displaystyle{ k }[/math] за [math]\displaystyle{ O(1) }[/math]; извлечение минимума идёт от текущего ведра вправо.

Идея. Объединить две очереди в одну. Стоимость решающим образом зависит от реализации: копирование массива ([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(1) }[/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 и диапазонные запросы.

Рис. 6. Стоимость операций по реализациям: зелёный — [math]\displaystyle{ O(1) }[/math], синий — [math]\displaystyle{ O(\log n) }[/math], красный — [math]\displaystyle{ O(n) }[/math]. Фибоначчиева куча выделяется амортизированным [math]\displaystyle{ O(1) }[/math] на Decrease-Key.

Трассировка примера

Последовательность операций над 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 по определению возвращает минимум и удаляет ровно его; повторяя, получаем все постусловия для остальных операций (они затрагивают лишь множество и ключ одного элемента).

[math]\displaystyle{ \blacksquare }[/math]

Инвариант конкретной реализации. Для двоичной кучи инвариант — «свойство кучи: ключ родителя не больше ключей детей». Из него следует, что корень — минимум: любой другой ключ лежит в поддереве некоторого ребёнка и потому не меньше корня по транзитивности. Это и есть уточнение (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-куча даст лучшие константы.

Где применяется

1. Коды Хаффмана. На каждом шаге берутся два символа с наименьшими частотами — два Extract-Min и одна Insert; сжатие за [math]\displaystyle{ O(n\log n) }[/math].
2. Слияние [math]\displaystyle{ k }[/math] отсортированных списков (k-way merge). Мини-куча из голов каждого списка выдаёт очередной элемент за [math]\displaystyle{ O(\log k) }[/math]; так работает внешняя сортировка.
3. Дискретно-событийное моделирование. Очередь событий упорядочена по времени срабатывания; Extract-Min берёт ближайшее событие, Insert добавляет новые. Для больших систем применяют calendar queue.
4. Планировщики ОС и сетей. Планирование задач по приоритету, weighted fair queuing и QoS выбирают очередной пакет/задачу по приоритету; здесь важна предсказуемость и борьба с «инверсией приоритетов».
5. Потоковые top-k, медиана и поиск в ширину по стоимости. Для «[math]\displaystyle{ k }[/math] наибольших в потоке» держат min-кучу размера [math]\displaystyle{ k }[/math]; для медианы — две кучи; в A*/best-first search приоритет — эвристическая оценка.
6. Ветви и границы (branch and bound). Очередь хранит подзадачи по нижней оценке; Extract-Min обрабатывает наиболее перспективную.
7. Алгоритм Дейкстры и Прим (рис. 7). Очередь хранит вершины по текущей оценке расстояния; Extract-Min даёт ближайшую непомеченную вершину, Decrease-Key — обновление оценки. На двоичной куче Дейкстра работает за [math]\displaystyle{ O((n+m)\log n) }[/math], на фибоначчиевой — за [math]\displaystyle{ O(m + n\log n) }[/math].

Рис. 7. Дейкстра: Extract-Min достаёт ближайшую вершину, Decrease-Key обновляет оценки её соседей; сложность зависит от выбора очереди.

Историческая справка

• 1964. Дж. У. Дж. Уильямс предложил двоичную кучу и heapsort ; в том же году Р. У. Флойд показал линейное построение кучи .
• 1969. Р. Диал предложил bucket-очередь для Дейкстры с малыми целочисленными весами .
• 1975–1977. П. ван Эмде Боас разработал структуру с операциями за [math]\displaystyle{ O(\log\log U) }[/math] на вселенной размера [math]\displaystyle{ U }[/math] .
• 1978. Ж. Вюйемен ввёл биномиальные кучи с быстрым слиянием .
• 1984–1987. М. Фредман и Р. Тарджан предложили фибоначчиевы кучи с амортизированным [math]\displaystyle{ O(1) }[/math] на decrease-key .
• 1986. Фредман, Седжвик, Слейтор и Тарджан предложили pairing-кучи — проще фибоначчиевых .
• 2000. Б. Шазель построил soft heap — приближённую очередь с [math]\displaystyle{ O(1) }[/math] амортизированно на операцию и управляемой долей ошибок .

Типичные ошибки и подводные камни

• Ожидание 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 переворачивает порядок.

Задачи для практики

1. Интерфейс vs реализация. Определите ADT-контракт очереди с приоритетом и докажите, что двоичная куча ему удовлетворяет. Подсказка: свойство кучи влечёт минимум в корне.
2. Индексированная куча. Реализуйте Decrease-Key через карту pos[id]; проверьте, что pos обновляется при каждом обмене. Ограничения: [math]\displaystyle{ n \le 10^6 }[/math].
3. Устойчивая очередь. Добавьте счётчик вставок к ключу и получите FIFO-порядок среди равных ключей. Подсказка: сравнивайте пары [math]\displaystyle{ (k, \text{seq}) }[/math] лексикографически.
4. Ленивая Дейкстра. Реализуйте Дейкстру со std::priority_queue и пропуском устаревших записей; сравните с индексированной кучей. Подсказка: храните пару [math]\displaystyle{ (\text{dist}, v) }[/math] и сверяйте dist[v].
5. k-way merge. Слейте [math]\displaystyle{ k }[/math] списков за [math]\displaystyle{ O(N\log k) }[/math]. Подсказка: min-куча из голов списков.
6. Top-k в потоке. Держите [math]\displaystyle{ k }[/math] наибольших за [math]\displaystyle{ O(\log k) }[/math] на элемент. Подсказка: min-куча размера [math]\displaystyle{ k }[/math].
7. Bucket queue. Реализуйте Диала для графа с малыми целыми весами. Подсказка: массив вёдер по расстояниям, указатель на текущий минимум.
8. Выбор структуры. Для трёх сценариев (частый 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].

Дополнительные источники

1. Knuth D. E. The Art of Computer Programming. Vol. 3: Sorting and Searching. — Addison-Wesley, 2nd ed., 1998. — §5.2.3.
2. Wikipedia: Priority queue. URL: https://en.wikipedia.org/wiki/Priority_queue.