Раздел «Алгоритмы».BinaryHeap:

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

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

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

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

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

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

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

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

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

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

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

Основное свойство кучи : Ключ родителя всегда меньше либо равен ключей детей.

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

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

Покажите, что число этажей в куче ограничено сверху логарифмом от числа элементов, а точнее \log_2 (N+1)

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

Edit drawing 'heap' (requires a Java enabled browser)

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

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

AlgorithmClasifyForm
Type: Теория
Scope: Структуры данных
Strategy:  
Language:  
Complexity: Medium