Большая куча
-
Двоичная куча и d-heap
- Двоичная куча — это 2-кучная, троичная куча — 3-кучная.
- Изобретена Дональдом Б. Джонсоном в 1975 году.
- Позволяет быстрее выполнять операции с пониженным приоритетом, но медленнее удалять минимум.
-
Структура данных
- Состоит из массива элементов с приоритетами.
- Элементы образуют полное d-образное дерево.
- В минимальной куче каждый элемент имеет приоритет не ниже родительского.
- В максимальной куче каждый элемент имеет приоритет не выше родительского.
-
Операции
- Удаление элемента: последний элемент перемещается на его место, длина массива уменьшается.
- Вставка элемента: элемент добавляется в конец массива, затем заменяется родительским элементом.
- Изменение приоритета: элемент заменяется дочерним элементом с наименьшим или наибольшим приоритетом.
-
Анализ
- Вставка нового элемента: O(log n / log d) времени.
- Удаление корневого элемента: O(d log n / log d) времени.
- Создание кучи: O(sd(n) ed(n)) времени.
-
Приложения
- Алгоритмы Дейкстры и Прима используют минимальную кучу.
- Общее время выполнения: O(m logm/n n) для d-ary кучи.
- Кучи Фибоначчи дают лучшее теоретическое время выполнения, но на практике d-ary кучи работают быстрее.
-
Практические аспекты
- 4-кучные кучи могут работать быстрее двоичных.
- Объемная куча быстрее, если превышает объем кэш-памяти.
- Двоичная куча требует больше промахов кэша и ошибок страниц.