Косая куча
-
Косая куча
- Структура данных кучи, реализованная в виде бинарного дерева
- Выгодна из-за способности объединяться быстрее бинарных куч
- Нет структурных ограничений, высота дерева не логарифмическая
-
Условия и операции
- Общий порядок в куче должен быть соблюден
- Каждая операция (добавление, удаление_мин, слияние) выполняется с использованием специального слияния косых куч
- Косая куча — самонастраивающаяся форма левой кучи
-
Анализ сложности
- Амортизированная сложность операций с косой кучей равна O(log n)
- Точная амортизированная сложность равна logφn, где φ = 1 + 5/2
-
Определение
- Куча с одним элементом является косой кучей
- Результат косого слияния двух косых куч также является косой кучей
-
Операции
- Объединение двух куч аналогично слиянию двух левых куч
- Нерекурсивное слияние требует сортировки поддеревьев
- Добавление значения аналогично слиянию дерева с одним узлом
- Удаление значения выполняется путем удаления корневого элемента и объединения его дочерних поддеревьев
-
Реализация
- Косые кучи просты в реализации на функциональных языках
- Пример реализации на Haskell
-
Рекомендации
- Внешние ссылки на анимацию и Java-апплет для моделирования куч