Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

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

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

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

При отсутствии структурных ограничений может показаться, что косая куча будет ужасно неэффективной. Однако можно использовать анализ амортизированной сложности, чтобы продемонстрировать, что все операции с косой кучей могут быть выполнены за O (log n ). [1] Фактически, с обозначением золотого сечения известно , что точная амортизированная сложность равна log φ n (приблизительно 1,44 log 2 n ). [2] [3]

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

Перекос кучи можно описать следующим рекурсивным определением: [ необходима ссылка ]

  • Куча, состоящая только из одного элемента, называется перекосом.
  • Результат слияния двух скошенных куч, а также перекос.

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

Слияние двух куч [ править ]

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

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


шаблон < класс  T ,  класс  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 ; если  ( firstRoot  ==  NULL )  return  secondRoot ; иначе,  если  ( 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 ;  }  иначе  вернуться _Merge ( secondRoot ,  firstRoot ); }

Перед:SkewHeapMerge1.svg


послеSkewHeapMerge7.svg

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

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

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

SkewHeapMerge1.svg

SkewHeapMerge2.svg

SkewHeapMerge3.svg

SkewHeapMerge4.svg

SkewHeapMerge5.svg

SkewHeapMerge6.svg

SkewHeapMerge7.svg

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

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

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

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

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

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

данные  SkewHeap  a  =  Пусто  |  Узел  a  ( SkewHeap  a )  ( SkewHeap  a )singleton  ::  Ord  a  =>  a  ->  SkewHeap  a singleton  x  =  Node  x  Empty  Пустообъединение  ::  Ord  => SkewHeap -> SkewHeap -> SkewHeap Empty ' объединение ` t2 = t2 t1 ' объединение ` Слейте = t1 t1 @ ( Node x1 l1 r1 ) ` объединение ` t2 @ ( Node x2 l2 r2 ) | x1 <= x2 = Узел x1 ( t2                                  ` Объединение `  r1 )  l1  |  в противном случае  =  Узел  x2  ( t1  ` объединение `  г2 )  l2вставить  ::  Ord  а  =>  а  ->  SkewHeap  а  ->  SkewHeap  с вставкой  х  кучи  =  одноплодной  х  ` объединение `  кучиextractMin  ::  Ord  => SkewHeap -> Может быть ( , SkewHeap ) extractMin Слейте = Nothing extractMin ( Node х л г ) = Просто ( х , л ` объединение ` г )

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

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

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

  • Конспект лекций, Skew Heaps, Йоркский университет
  • Анимации, сравнивающие левую кучу и косую кучу, Йоркский университет
  • Симуляция перекоса кучи Javascript, Университет Сан-Франциско
  • Java-апплет для моделирования куч, Университет штата Канзас