2.3.3 — слабый инвариант ради одной операции: достать минимум быстро2.3.3 — a weak invariant in exchange for one fast operation: get the minimum
Дерево поиска (2.3.2) держит полный порядок — можно найти любой ключ, следующий по величине, диапазон. Куча платит меньше за куда более узкую задачу: она вообще не поддерживает полный порядок, а гарантирует только одно — извлечь минимальный (или максимальный) элемент за O(log n), не заботясь о порядке между остальными. Это структура данных под очередь с приоритетом: не "найти X", а "дай мне сейчас самый важный элемент". Здесь: от бинарной кучи в массиве — через обобщение на d потомков — к кучам, которые умеют быстро сливаться друг с другом (двоичное дерево этого не может), и к структурам с амортизированной O(1) вставкой ценой практической сложности.A search tree (2.3.2) maintains full order — you can find any key, the next-largest one, a range. A heap pays less for a much narrower job: it doesn't maintain full order at all, guaranteeing only one thing — extract the minimum (or maximum) element in O(log n), without caring about the order among the rest. This is the data structure behind a priority queue: not "find X" but "give me the most important element right now." Here: from a binary heap in an array — through a generalization to d children — to heaps that can merge with each other quickly (a binary heap can't do that) — to structures with amortized O(1) insertion at the cost of practical complexity.
Инвариант кучи — heap-order: ключ родителя ≤ (или ≥, для max-кучи) ключей его детей. Это намного слабее инварианта BST — между двумя братьями-узлами вообще ничего не гарантируется, куча не отсортирована, и обход по уровням не даёт отсортированную последовательность. Слабый инвариант — не недостаток, а осознанный выбор: он дешевле в поддержании и достаточен для одной операции — extract-min. Бинарная куча (2.3.3.1) хранит эту идею в чистом виде: полное бинарное дерево, упакованное в массив без единого указателя. d-арная куча (2.3.3.2) меняет branching factor, чтобы сдвинуть баланс между вставкой и удалением в нужную сторону под конкретную нагрузку. Дальше три структуры решают задачу, которую обычная куча решает плохо или вообще не решает: слияние двух куч. Бинарная куча сливается за O(n); биномиальная куча (2.3.3.3) — за O(log n) через механизм, буквально совпадающий с двоичным сложением с переносом. Куча Фибоначчи (2.3.3.4) доводит амортизированную стоимость вставки и decrease-key до O(1) ценой "ленивости" — но с высокой практической сложностью. Парная куча (2.3.3.5) даёт почти ту же практическую производительность гораздо более простой структурой, хотя строгий анализ decrease-key для неё до сих пор не завершён.A heap's invariant is heap-order: a parent's key is ≤ (or ≥, for a max-heap) its children's keys. That's much weaker than the BST invariant — nothing at all is guaranteed between two sibling nodes, a heap isn't sorted, and a level-order traversal doesn't yield a sorted sequence. The weak invariant isn't a shortcoming but a deliberate choice: it's cheaper to maintain and sufficient for one operation — extract-min. A binary heap (2.3.3.1) stores this idea in its purest form: a complete binary tree packed into an array with not a single pointer. A d-ary heap (2.3.3.2) changes the branching factor to shift the balance between insertion and deletion the way a specific workload needs. From there, three structures solve a problem a plain heap handles poorly or not at all: merging two heaps. A binary heap merges in O(n); a binomial heap (2.3.3.3) merges in O(log n) via a mechanism that literally matches binary addition with carrying. A Fibonacci heap (2.3.3.4) pushes the amortized cost of insertion and decrease-key down to O(1) at the price of "laziness" — but with high practical complexity. A pairing heap (2.3.3.5) delivers nearly the same practical performance with a far simpler structure, even though a tight analysis of its decrease-key is still an open problem.
чем "ленивее" merge (просто конкатенация вместо немедленной перестройки), тем дешевле insert/decrease-key — но тем дороже и сложнее устроен extract-minthe lazier the merge (plain concatenation instead of immediate restructuring), the cheaper insert/decrease-key — but the pricier and more intricate extract-min becomes
Порядок карточек — от самой простой реализации в массиве до самых сложных амортизированных структур, каждая следующая мотивирована ограничением предыдущей. Полный разбор — на отдельной странице по ссылке в названии.The card order goes from the simplest array-based implementation to the most elaborate amortized structures, each one motivated by the previous one's limitation. The full writeup is on its own page via the name link.
Первая карточка — бинарная куча, база и мера производительности для всех остальных. Вторая — d-арная куча — простое обобщение branching factor, полезное там, где вставка/decrease-key доминируют над извлечением. Третья, четвёртая и пятая карточки решают одну и ту же дополнительную задачу — дешёвое слияние двух куч, — которую бинарная и d-арная куча не умеют вовсе (только пересборка за O(n)): биномиальная куча даёт строгий O(log n) через явную структуру леса; куча Фибоначчи и парная куча идут дальше — амортизированный O(1) на вставку и (для Фибоначчи, доказанно; для парной — эмпирически) на decrease-key, за счёт "ленивого" объединения без немедленной перестройки.The first card is the binary heap, the baseline and performance yardstick for everything else. The second — d-ary heap — is a simple generalization of the branching factor, useful wherever insertion/decrease-key dominates over extraction. The third, fourth, and fifth cards solve the same extra problem — cheap merging of two heaps — that a binary or d-ary heap can't do at all (only an O(n) rebuild): a binomial heap gives a strict O(log n) via an explicit forest structure; a Fibonacci heap and a pairing heap go further — amortized O(1) insertion and (for Fibonacci, provably; for pairing, empirically) decrease-key, by "lazily" combining without immediate restructuring.
Практическая реализация кратчайших путей (Дейкстра) и минимального остовного дерева (Прим) почти всегда использует бинарную кучу как очередь с приоритетом по весу ребра; d-арная куча (часто d=4) — стандартная оптимизация, когда decrease-key/insert доминируют над числом извлечений, как в плотных графах.A practical implementation of shortest paths (Dijkstra) and a minimum spanning tree (Prim) almost always uses a binary heap as a priority queue keyed by edge weight; a d-ary heap (often d=4) is a standard optimization when decrease-key/insert dominate over the number of extractions, as in dense graphs.
C++ std::priority_queue, Python heapq и Java java.util.PriorityQueue — все реализованы как обычная бинарная куча в массиве, несмотря на существование куч с лучшей асимптотикой (Фибоначчи, парных). Причина простая: константы и cache locality массива побеждают на реальных размерах входа.C++'s std::priority_queue, Python's heapq, and Java's java.util.PriorityQueue are all implemented as a plain array-based binary heap, despite heaps with better asymptotics existing (Fibonacci, pairing). The reason is simple: an array's constants and cache locality win at real-world input sizes.
Алгоритм Хаффмана строит дерево кодирования, на каждом шаге извлекая из очереди с приоритетом два узла с наименьшей частотой и объединяя их в новый узел — классический пример бинарной кучи как рабочей лошадки жадного алгоритма (подробный разбор — в 2.4.3, жадные алгоритмы).Huffman's algorithm builds a coding tree by repeatedly extracting the two lowest-frequency nodes from a priority queue and merging them into a new node — a classic example of a binary heap as the workhorse of a greedy algorithm (covered in depth in 2.4.3, greedy algorithms).
Протоколы маршрутизации с состоянием канала, такие как OSPF, вычисляют кратчайший путь до каждого узла сети алгоритмом Дейкстры поверх очереди с приоритетом на основе кучи — та же структура, что используется для кратчайших путей в графах общего назначения, только на графе топологии сети.Link-state routing protocols such as OSPF compute the shortest path to every network node via Dijkstra's algorithm on top of a heap-based priority queue — the same structure used for general-purpose graph shortest paths, just applied to the network topology graph.
Системы дискретно-событийного моделирования (сетевые симуляторы, симуляторы очередей обслуживания, event-driven тестовые стенды) хранят будущие события в очереди с приоритетом по временной метке — extract-min всегда даёт следующее по времени событие, а новые события вставляются по мере обработки текущих.Discrete-event simulation systems (network simulators, queueing-system simulators, event-driven test harnesses) keep future events in a priority queue keyed by timestamp — extract-min always yields the next event in time, and new events get inserted as the current ones are processed.
Куча гарантирует только parent ≤ child (для min-кучи) — это не значит, что массив кучи отсортирован. Гарантирован только корень как минимум; между братьями-узлами (и вообще между любыми двумя узлами не в отношении предок-потомок) нет никакого определённого порядка. Итерация по массиву кучи "как есть" — не сортировка, и полагаться на неё как на отсортированную последовательность — частая ошибка.A heap only guarantees parent ≤ child (for a min-heap) — that doesn't mean the heap's array is sorted. Only the root is guaranteed to be the minimum; between sibling nodes (and between any two nodes not in an ancestor-descendant relationship) there's no defined order at all. Iterating the heap's array "as is" is not a sort, and relying on it as a sorted sequence is a common mistake.
На бинарной и d-арной куче decrease-key стоит O(log n) — после уменьшения ключа нужен sift-up. На куче Фибоначчи decrease-key амортизированно O(1) — это единственная причина, по которой куча Фибоначчи вообще существует и упоминается в асимптотике алгоритма Дейкстры/Прима O(E + V log V): без O(1) decrease-key эта граница недостижима. Парная куча по эмпирике ведёт себя похоже, но строгого доказательства O(1) для неё нет.On a binary or d-ary heap decrease-key costs O(log n) — decreasing a key requires a sift-up. On a Fibonacci heap decrease-key is amortized O(1) — that's the entire reason a Fibonacci heap exists and shows up in the O(E + V log V) asymptotic bound for Dijkstra's/Prim's algorithm: without O(1) decrease-key, that bound is unreachable. A pairing heap behaves similarly in practice, but no tight O(1) proof exists for it.
Лучшая асимптотика не означает лучшую производительность на реальных размерах входа: у кучи Фибоначчи большие константы, плохая локальность кэша (много отдельно аллоцированных узлов и указателей) и заметно более сложная реализация. Парная куча или даже обычная бинарная куча часто выигрывают на практике — классическая ловушка "асимптотика против реального быстродействия".Better asymptotics doesn't mean better performance at real-world input sizes: a Fibonacci heap has large constants, poor cache locality (many separately allocated nodes and pointers), and a noticeably more complex implementation. A pairing heap or even a plain binary heap often wins in practice — the classic "asymptotic complexity vs. real-world performance" trap.