Двоичная куча
Описание структуры
Структура "Двочная куча" (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
. См. рисунок. - Если вы хотите иметь возможность
обновлять положение элементов в куче или удалять
проихвольный элемент из кучи, но к каждому элементу
необходимо добавить поле
индекс элемента в массиве кучи
. То есть работать с тройкой (ключ, индекс в массиве кучи, значение), а не с парой (ключ, значение).

Реализации двоичной кучи на различных языках
Примеры задач, которые решаются с помощью двоичной кучи
- Найти K максимальных различных чисел из N (K порядка 100, а N порядка 10^9)
- HeapSort сортировка работающая N log N в реднем и в худшем случае.
- Максимальное покрывающее (остовное) дерево
- Алгоритм Дейкстры поиска кратчайших путей в графе из данной вершины.
- Очередь с приоритетами организация заданий (процессов) с приоритетами в операционных системах
AlgorithmClasifyForm | |
---|---|
Type: | Теория |
Scope: | Структуры данных |
Strategy: | |
Language: | |
Complexity: | Medium |