Двоичная куча

Описание структуры

Структура "Двочная куча" (Binary Heap) позволяет хранить пары ключ-значение (key-value), и быстро выполнять операцию извлечения пары с минимальным значением ключа и операцию добавления новых пар.

С помощью двоичной кучи обычно реализуется АТД Очередь с приоритетами --- структура, позволяющая хранить объекты с приоритетами (например задания с приоритетами), извлекать самый приоритетный объект, добавлять новые объекты, быстро обновлять их приоритеты.

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

Для того, чтобы взять самый приоритетный объект, нужно взять первый элемент массива (списка) и удалить его, перенеся начало на второй элемент.

Но эти структуры данных оказываются не самыми эффективными. Операция обновления в них стоит дорого (в среднем).

Итак нам нужна структура данных, со следующим интерфейсом:

• Insert(a) — добавить элемента a
• ExtractMin() — извлечь элемент с минимальным ключем (максимальным приоритетом)
• Delete(a) — удалить из кучи элемент a

Существуют структуры данных, позволяющие делать каждую из этих трёх операций за логарифмическое (по числу элементов в куче) время. Наиболее простая из них — это бинарная куча.

Она реализуется, с помощью бинарного дерева.

В частности, в вершине кучи (корне дерева) будет находится элемент с минимальным ключем (с наибольшим приоритетом). Упорядоченность, которая возникает в куче слабее чем обычная упорядоченность элементов массиве. И эту упорядоченность можно получит быстрее — за линейное время, нежели отсортированный массив — за N log N.

Все операции с кучей выполняются за log N операций в худшем случае:

• Insert: Поместим новый элемент в конец массива. Посмотрим на его родителя и проверим свойство кучи. Если оно нарушено — поменяем его местами с родителем и снова проверим свойство кучи. Таким образом элемент будет "всплывать" пока не найдет для себя подходящего места в куче. Если его ключ самый маленький, то он высплывет до самого конца и окажется в вершине кучи. Число шагов всплытия меньше чем высота дерева. Размер кучи следует увеличить на 1.
• ExtractMin: Возьмём вершину кучи и отложим в сторону, чтобы в конце вернуть её в качестве результата выполнения функции. Переместим в вершину кучи самый последний элемент кучи (с наибольшим индексом) и начнем его "топить": проверим, что его ключ меньше, чем ключи детей, и если это не так, поменяем его местами с ребенком с наименьшим ключом. После операции "топления" нужно еще раз проверить свойство кучи и опять поменять с "наименьшим" ребенком если это надо, и так топить элемент пока он не в станет в подходящее для него место. Размер кучи уменьшается на 1. Число шагов топления не более, чем высота кучи.

Покажите, что число этажей в куче ограничено сверху логарифмом от числа элементов, а точнее

Важные моменты:

• Элементы дерева можно хранить в памяти просто как массив (сплошной массив без дырок), в котором у элемента с индексом i левый ребенок имеет индекс 2*i, а правый — 2*i+1. См. рисунок.
• Если вы хотите иметь возможность обновлять положение элементов в куче или удалять проихвольный элемент из кучи, но к каждому элементу необходимо добавить поле индекс элемента в массиве кучи. То есть работать с тройкой (ключ, индекс в массиве кучи, значение), а не с парой (ключ, значение).

Реализации двоичной кучи на различных языках

• Perl
• C++

Примеры задач, которые решаются с помощью двоичной кучи

• Найти K максимальных различных чисел из N (K порядка 100, а N порядка 10^9)
• HeapSort — сортировка работающая N log N в реднем и в худшем случае.
• Максимальное покрывающее (остовное) дерево
• Алгоритм Дейкстры поиска кратчайших путей в графе из данной вершины.
• Очередь с приоритетами — организация заданий (процессов) с приоритетами в операционных системах