Двоичная куча
-
Определение и свойства двоичной кучи
- Двоичная куча — это полное двоичное дерево с упорядоченными элементами.
- Элементы хранятся в массиве, где каждый элемент имеет родителя и двух детей.
- Свойства кучи включают сохранение порядка элементов и возможность быстрого поиска минимума или максимума.
-
Реализация на основе массива
- Элементы хранятся в массиве с индексами от 0 до n-1.
- Каждый элемент имеет двух детей с индексами 2i+1 и 2i+2, если корень находится в индексе 0, или 2i и 2i+1, если корень находится в индексе 1.
- Операция подъема или опускания элемента может быть выполнена путем изменения порядка элементов в массиве.
-
Динамическое расширение и операции
- Куча может быть расширена до любого размера, при этом операции подъема и опускания выполняются быстро.
- Для больших массивов и использования виртуальной памяти хранение элементов неэффективно.
-
Бинарные кучи и их оптимизация
- Бинарные кучи хранят поддеревья на одной странице, что сокращает количество доступных страниц в десять раз.
- Объединение и разделение двух куч может быть выполнено за линейное время.
- Существуют алгоритмы для объединения и разделения куч, которые требуют меньше сравнений ключей.
-
Индексация и родительские узлы
- Выведены уравнения для определения индексов дочерних и родительских узлов в куче.
- Уравнения применимы к кучам с корнем в индексе 0 или 1.
-
Связанные структуры и временные сложности
- Двоичная куча является частным случаем двоичной кучи с d = 2.
- Представлены временные сложности различных структур данных кучи.
-
Рекомендации
- Ссылки на внешние ресурсы для дополнительной информации и реализации двоичных куч на C.
Полный текст статьи: