Куча спариваний
-
Описание парных куч
- Парные кучи — это упорядоченные по кучам многоходовые древовидные структуры.
- Они были представлены Майклом Фредманом, Робертом Седжвиком, Дэниелом Слейтором и Робертом Тарьяном в 1986 году.
- Парные кучи считаются «надежным выбором» для реализации алгоритмов, таких как MST-алгоритм Prim.
-
Операции парных куч
- find-min: возвращает верхний элемент кучи.
- объединение: сравнивает два корневых элемента, меньший остается корнем, больший добавляется как дочерний.
- вставка: создает новую кучу для вставленного элемента и объединяет её с исходной кучей.
- уменьшающий ключ: удаляет поддерево, заменяет ключ ключом меньшего размера и объединяет результат.
- удалить-минимум: удаляет корень и объединяет поддеревья до одного дерева.
-
Временная сложность
- Удаление-минимум: O(log n).
- Поиск-min, объединение и вставка: O(1).
- Уменьшение ключа: O(2^2 log log n) амортизированное время.
- Elmasry: O(log log n) амортизированное время для сопряжения куч.
-
Практические аспекты
- Парные кучи имеют асимптотическую производительность хуже, чем кучи Фибоначчи.
- На практике парные кучи часто работают быстрее, чем другие реализации кучи.
- Парные кучи могут быть быстрее, чем другие кучи на основе указателей.
-
Структура данных
- Парная куча — это либо пустая куча, либо парное дерево с корневым элементом и списком поддеревьев.
- Реализация на основе указателей использует три указателя на узел.
-
Рекомендации
- Луис Вассерман обсуждает сопряжение куч в Haskell.
- Сартадж Сахни описывает парные кучи.