Косая куча

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

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

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

шаблон  <  класс   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  ;      if   (  firstRoot   ==   NULL  )          вернуть   SecondRoot  ;      иначе,   если   (  второй корень   ==   NULL  )          вернуть   первый корень  ;      if   (  sh_compare  ->  Less  (  firstRoot  ->  key  ,   SecondRoot  ->  key  ))      {          SkewNode  <  T  >*   tempHeap   =   firstRoot  ->  rightNode  ;          firstRoot  ->  rightNode   =   firstRoot  ->  leftNode  ;          firstRoot  ->  leftNode   =   Merge  (  SecondRoot  ,   tempHeap  );          вернуть   первый корень  ;      }      Еще          верните   слияние  (  второй корень  ,   первый корень  );  }

До:

после

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

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

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

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

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

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

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

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

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

данные   SkewHeap   a   =   Пусто                  |   Node   a   (  SkewHeap   a  )   (  SkewHeap   a  )  синглтон   ::   Ord   a   =>   a   ->   SkewHeap   a  синглтон   x   =   Node   x   Empty   Empty  Union   ::   Ord   a   =>   SkewHeap   a   ->   SkewHeap   a   ->   SkewHeap   a  Empty                `  union  `   t2                   =   t2  t1                   `  объединение  `   Empty                =   t1  t1  @  (  Узел   x1   l1   r1  )   `  объединение  `   t2  @  (  Узел   x2   l2   r2  )     |   x1   <   x2                                   =   Узел   x1   (  t2   `  union`  r1   )  |   l1     =   иначе                                  =   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          =   Ничего  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]