Введение
Склонная куча (или самонастраивающаяся куча) — это структура данных кучи, реализованная в виде двоичного дерева. Склонные кучи эффективны благодаря своей способности к более быстрому слиянию, чем у бинарных куч. В отличие от бинарных куч, структурных ограничений нет, поэтому не гарантируется, что высота дерева будет логарифмической. Должны выполняться только два условия:
Должен соблюдаться общий порядок кучи.
Любая операция (добавление, удаление минимума, слияние) над двумя склонными кучами должна выполняться с использованием специального слияния склонных куч. Склонная куча является самонастраивающейся формой левой кучи, которая пытается поддерживать баланс, безусловно меняя местами все узлы на пути слияния при слиянии двух куч. (Операция слияния также используется при добавлении и удалении элементов.) Несмотря на отсутствие структурных ограничений, может показаться, что склонная куча будет крайне неэффективной. Однако, анализ амортизированной сложности позволяет доказать, что все операции над склонной кучей могут быть выполнены за O(log n). Фактически, если φ обозначает золотое сечение, то точная амортизированная сложность известна как logφ n (приблизительно 1,44 log2 n).
The general heap order must be enforced
Every operation (add, remove min, merge) on two skew heaps must be done using a special skew heap merge. A skew heap is a self adjusting form of a leftist heap which attempts to maintain balance by unconditionally swapping all nodes in the merge path when merging two heaps. (The merge operation is also used when adding and removing values.) With no structural constraints, it may seem that a skew heap would be horribly inefficient. However, amortized complexity analysis can be used to demonstrate that all operations on a skew heap can be done in O(log n). In fact, with denoting the golden ratio, the exact amortized complexity is known to be logφ n (approximately 1.44 log2 n).
Нерекурсивное слияние
В качестве альтернативы существует нерекурсивный подход, который более многословен и требует предварительной сортировки. Разделите каждую кучу на поддеревья, прерывая каждый путь. (От корневого узла отделите правый узел и сделайте правого потомка самостоятельным поддеревом.) В результате получится набор деревьев, у корня которых либо только левый потомок, либо нет потомков вообще. Отсортируйте поддеревья по возрастанию, основываясь на значении корневого узла каждого поддерева. Пока существует несколько поддеревьев, итеративно объединяйте последние два (справа налево). Если у корня предпоследнего поддерева есть левый потомок, поменяйте его местами с правым потомком. Присоедините корень последнего поддерева как левого потомка предпоследнего поддерева.
Добавление значений
Добавление значения в наклонную кучу аналогично объединению дерева из одного узла с исходной кучей.
Удаление значений
Удаление первого элемента в куче может быть выполнено удалением корня и объединением его дочерних поддеревьев.