Косая куча

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

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

Косая куча — это самонастраивающаяся форма левой кучи , которая пытается поддерживать баланс путем безусловной замены всех узлов на пути слияния при слиянии двух куч. (Операция слияния также используется при добавлении и удалении значений.) При отсутствии структурных ограничений может показаться, что косая куча будет ужасно неэффективной. Однако анализ амортизированной сложности можно использовать, чтобы продемонстрировать, что все операции с косой кучей могут быть выполнены за O(log n ). ^[1] Фактически, с ${\textstyle \varphi ={\frac {1+{\sqrt {5}}}{2}}}$ обозначая золотое сечение , точная амортизированная сложность, как известно, равна log _φ n (приблизительно 1,44 log ₂ n ). ^[2]^[3]

Определение [ править ]

Косые кучи можно описать с помощью следующего рекурсивного определения: ^{[ нужна ссылка ]}^{[ нужны разъяснения ]}

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

Операции [ править ]

Объединение двух куч [ править ]

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

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

template<class T, class CompareFunction>
SkewNode<T>* CSkewHeap<T, CompareFunction>::Merge(SkewNode<T>* root_1, SkewNode<T>* root_2)
{
    SkewNode<T>* firstRoot = root_1;
    SkewNode<T>* secondRoot = root_2;

    if (firstRoot == NULL)
        return secondRoot;

    else if (secondRoot == NULL)
        return firstRoot;

    if (sh_compare->Less(firstRoot->key, secondRoot->key))
    {
        SkewNode<T>* tempHeap = firstRoot->rightNode;
        firstRoot->rightNode = firstRoot->leftNode;
        firstRoot->leftNode = Merge(secondRoot, tempHeap);
        return firstRoot;
    }
    else
        return Merge(secondRoot, firstRoot);
}

До:

после

Нерекурсивное слияние [ править ]

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

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

Добавление значений [ править ]

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

Удаление значений [ править ]

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

Реализация [ править ]

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

data SkewHeap a = Empty
                | Node a (SkewHeap a) (SkewHeap a)

singleton :: Ord a => a -> SkewHeap a
singleton x = Node x Empty Empty

union :: Ord a => SkewHeap a -> SkewHeap a -> SkewHeap a
Empty              `union` t2                 = t2
t1                 `union` Empty              = t1
t1@(Node x1 l1 r1) `union` t2@(Node x2 l2 r2)
   | x1 <= x2                                 = Node x1 (t2 `union` r1) l1
   | otherwise                                = Node x2 (t1 `union` r2) l2

insert :: Ord a => a -> SkewHeap a -> SkewHeap a
insert x heap = singleton x `union` heap

extractMin :: Ord a => SkewHeap a -> Maybe (a, SkewHeap a)
extractMin Empty        = Nothing
extractMin (Node x l r) = Just (x, l `union` r)

Ссылки [ править ]

^ Слитор, Дэниел Доминик ; Тарьян, Роберт Эндре (февраль 1986 г.). «Саморегулирующиеся кучи» . SIAM Journal по вычислительной технике . 15 (1): 52–69. CiteSeerX 10.1.1.93.6678 . дои : 10.1137/0215004 . ISSN 0097-5397 .
^ Калдевайдж, Энн; Шенмейкерс, Берри (1991). «Вывод более точной границы для косых куч сверху вниз» (PDF) . Письма об обработке информации . 37 (5): 265–271. CiteSeerX 10.1.1.56.8717 . дои : 10.1016/0020-0190(91)90218-7 .
^ Шенмейкерс, Берри (1997). «Точная нижняя граница для косых куч сверху вниз» (PDF) . Письма об обработке информации . 61 (5): 279–284. CiteSeerX 10.1.1.47.447 . дои : 10.1016/S0020-0190(97)00028-8 . S2CID 11288837 .

Внешние ссылки [ править ]

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

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

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

[1]

[2]

[3]