Перекос кучи - Skew heap

А косая куча (или же саморегулирующаяся куча) это куча структура данных реализовано как двоичное дерево. Скошенные кучи выгодны из-за их способности объединяться быстрее, чем двоичные кучи. По сравнению с двоичные кучи, нет никаких структурных ограничений, поэтому нет гарантии, что высота дерева будет логарифмической. Должны быть выполнены только два условия:

Должен быть соблюден общий порядок кучи
Каждая операция (добавление, удаление_мин, слияние) над двумя перекосами должна выполняться с использованием специального слияние с перекосом кучи.

Косая куча - это саморегулирующаяся форма левая куча который пытается поддерживать баланс, безоговорочно меняя местами все узлы на пути слияния при слиянии двух куч. (Операция слияния также используется при добавлении и удалении значений.)

При отсутствии структурных ограничений может показаться, что наклонная куча ужасно неэффективна. Тем не мение, анализ амортизированной сложности может использоваться для демонстрации того, что все операции с косой кучей могут быть выполнены за O (журнал п).^[1]Фактически, с φ= (1 + √5) / 2, обозначающее золотое сечение, известно, что точная амортизированная сложность равна log_φ п (приблизительно 1,44 журнала₂ п).^[2]^[3]

Определение

Перекос кучи можно описать следующим образом рекурсивный определение:^{[нужна цитата ]}

Куча, состоящая только из одного элемента, называется перекосом.
Результат перекос слияния две косые кучи ${ displaystyle sh_ {1}}$ и ${ displaystyle sh_ {2}}$ это тоже косая куча.

Операции

Слияние двух куч

Когда нужно объединить две косые кучи, мы можем использовать аналогичный процесс, как слияние двух левые кучи:

Сравните корни двух куч; позволять п - куча с меньшим корнем, а q - другая куча. Позволять р быть именем получившейся новой кучи.
Пусть корень r будет корнем п (меньший корень), и пусть правое поддерево r будет левым поддеревом p.
Теперь вычислите левое поддерево r, рекурсивно объединяя правое поддерево p с q.

шаблон<учебный класс Т, учебный класс Сравнить>SkewNode<Т>* CSkewHeap<Т, Сравнить>::_Merge(SkewNode<Т>* root_1, SkewNode<Т>* корень_2){    SkewNode<Т>* firstRoot = root_1;    SkewNode<Т>* secondRoot = корень_2;    если (firstRoot == НОЛЬ)        возвращаться secondRoot;    еще если (secondRoot == НОЛЬ)        возвращаться firstRoot;    если (sh_compare->Меньше(firstRoot->ключ, secondRoot->ключ))    {        SkewNode<Т>* tempHeap = firstRoot->rightNode;        firstRoot->rightNode = firstRoot->leftNode;        firstRoot->leftNode = _Merge(secondRoot, tempHeap);        возвращаться firstRoot;    }    еще        возвращаться _Merge(secondRoot, firstRoot);}

Перед:

после

Нерекурсивное слияние

В качестве альтернативы существует нерекурсивный подход, который является более многословным и требует некоторой сортировки с самого начала.

Разделите каждую кучу на поддеревья, разрезав каждый путь. (От корневого узла отделите правый узел и сделайте правый дочерний элемент своим собственным поддеревом.) Это приведет к набору деревьев, в которых у корня либо есть только левый дочерний элемент, либо нет дочерних элементов вообще.
Отсортируйте поддеревья в порядке возрастания на основе значения корневого узла каждого поддерева.
Пока существует несколько поддеревьев, итеративно рекомбинируйте последние два (справа налево).
- Если у корня предпоследнего поддерева есть левый дочерний элемент, замените его правым дочерним элементом.
- Свяжите корень последнего поддерева как левый дочерний элемент предпоследнего поддерева.

Добавление значений

Добавление значения в кучу перекоса похоже на объединение дерева с одним узлом вместе с исходным деревом.

Удаление ценностей

Удаление первого значения в куче может быть выполнено путем удаления корня и объединения его дочерних поддеревьев.

Выполнение

Во многих функциональных языках реализовать косую кучу чрезвычайно просто. Вот полный пример реализации на Haskell.

данные SkewHeap а = Пустой                | Узел а (SkewHeap а) (SkewHeap а)одиночка :: Ord а => а -> SkewHeap аодиночка Икс = Узел Икс Пустой Пустойсоюз :: Ord а => SkewHeap а -> SkewHeap а -> SkewHeap аПустой              `союз` t2                 = t2t1                 `союз` Пустой              = t1t1@(Узел x1 l1 r1) `союз` t2@(Узел x2 l2 r2)   | x1 <= x2                                 = Узел x1 (t2 `союз` r1) l1   | иначе                                = Узел x2 (t1 `союз` r2) l2вставлять :: Ord а => а -> SkewHeap а -> SkewHeap авставлять Икс куча = одиночка Икс `союз` кучаextractMin :: Ord а => SkewHeap а -> Может быть (а, SkewHeap а)extractMin Пустой        = НичегоextractMin (Узел Икс л р) = Только (Икс, л `союз` р)

внешняя ссылка

[1] Слеатор, Дэниел Доминик; Тарджан, Роберт Эндре (Февраль 1986 г.). «Саморегулирующиеся кучи». SIAM Журнал по вычислениям. 15 (1): 52–69. CiteSeerX 10.1.1.93.6678. Дои:10.1137/0215004. ISSN 0097-5397.

[2] Калдевай, Энн; Schoenmakers, Берри (1991). «Вывод более жесткой границы для наклонных куч сверху вниз» (PDF). Письма об обработке информации. 37 (5): 265–271. CiteSeerX 10.1.1.56.8717. Дои:10.1016/0020-0190(91)90218-7.

[3] Schoenmakers, Берри (1997). «Жесткая нижняя граница для кучи с перекосом сверху вниз» (PDF). Письма об обработке информации. 61 (5): 279–284. CiteSeerX 10.1.1.47.447. Дои:10.1016 / S0020-0190 (97) 00028-8.

[1]

[2]

[3]