Косая биномиальная куча

Косая биномиальная куча
Косая биномиальная куча
Тип	куча
Изобретенный	1996
Изобретён	Герт Столтинг Бродал и Крис Окасаки
Операция
Временная сложность в обозначении большого О
Операция	Средний
Вставлять	я (1)
Найти-мин	я (1)
Удалить-мин.	О(логарифм n )
Клавиша уменьшения	О(логарифм n )
Объединить	О(логарифм n )
Пространственная сложность

В информатике ( косая биномиальная куча или косая биномиальная очередь ) — это структура данных для операций приоритетной очереди . Это вариант биномиальной кучи , который в худшем случае поддерживает операции вставки с постоянным временем, а не с амортизированным временем .

Мотивация [ править ]

Так же, как биномиальные кучи основаны на двоичной системе счисления , косые двоичные кучи основаны на асимметричной двоичной системе счисления . ^[1] Обычные биномиальные кучи страдают от наихудшей логарифмической сложности при вставке, поскольку операция переноса может быть каскадной, аналогично двоичному сложению. Косые биномиальные кучи основаны на косой двоичной системе счисления, где $k$ -я цифра (с нулевым индексом) представляет $2^{k+1}-1$ , вместо $2^{k}$ . Цифры могут быть либо 0, либо 1, за исключением самой младшей ненулевой цифры, которая может быть 2. Преимущество этой системы состоит в том, что требуется не более одной операции переноса. Например, 60 представлено как 11 200 в асимметричном двоичном формате (31 + 15 + 7 + 7), а добавление 1 дает 12 000 (31 + 15 + 15). Поскольку следующая старшая цифра гарантированно не равна 2, перенос выполняется не более одного раза. Эта аналогия применяется к операции вставки путем введения троичных (косых) связей, которые связывают три дерева вместе. Это позволяет операции вставки выполняться за постоянное время.

Структура [ править ]

Косая биномиальная куча — это лес косых биномиальных деревьев , которые определяются индуктивно:

Косое биномиальное дерево ранга 0 является одноэлементным узлом.
Косое биномиальное дерево рангов $r+1$ $r+1$ можно построить тремя способами:
- простая ссылка связывает два ранга $r$ деревья, что делает одно крайним левым дочерним элементом другого;
- соединяет Косая связь типа А три дерева. Два ранга $r$ деревья становятся потомками дерева ранга 0;
- связывает Косая связь типа B три дерева. Дерево ранга 0 и ранг $r$ дерево станет самым левым потомком другого ранга $r$ дерево.

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

Следующий код OCaml демонстрирует операции связывания:

введите   '  a   heap   =   '  деревьев   )   список   и   '  a   Tree   =   Tree   of   '  a   *   int   *   '  деревьев   (   список   let   Rank   (  Tree   _,   r  ,   _)   =   r  let   simple_link   (  Tree   (  k1  ,   r  ,   c1  )   as   t1  )   (  Дерево   (  k2  ,   r  ,   c2  )   as   t2  )   =    если   k1   <=   k2   то      Дерево   (  k1  ,   r   +   1  ,   t2   ::   c1  )    иначе      Дерево   (  k2  ,   r   +   1  ,   t1   ::   c2  )      пусть   skew_link   k1   (  Дерево   (  k2  ,   r  ,   c2  )   как   t2  )   (  Дерево   (  k3  ,   r  ,   c3  )   как   t3  )   =    если   k1   <=   k2   &&   k1   <=   k3,   то   (* тип A *)      Дерево   (  k1  ,   r   +   1  ,   [  t2  ;   t3  ])    else                           (* тип B *)      пусть   t1   =   Tree   (  k1  ,   0  ,   []  )   в том случае      , если   k2   <=   k3,   то        Tree   (  k2  ,   r   +   1  ,   t1   ::   t3   ::   c2  )      else        Дерево   (  k3  ,   r   +   1  ,   t1   ::   t2   ::   c3  )

Из этих свойств можно вывести, что корень ранга $r$ скошенное биномиальное дерево имеет до $2r$ дети. Количество узлов в косом биномиальном дереве $t$ ранга $r$ также ограничено $2^{r}\leq |t|\leq 2^{r+1}-1$ . Поскольку деревья одного и того же ранга могут иметь разное количество узлов, может существовать несколько способов распределения рангов в куче.

Эти конструкции можно рассматривать как обобщение бинарных и биномиальных деревьев. Косое биномиальное дерево, построенное с использованием только простых связей, является обычным биномиальным деревом, а использование только косых связей типа А приводит к идеально сбалансированному двоичному дереву.

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

Найти-мин [ править ]

Найдите в списке корней узел, содержащий минимальный ключ. Это занимает $O(\log n)$ время.

В императивной настройке можно сохранить указатель на корень, содержащий минимальный ключ, разрешая доступ в $O(1)$ время. Этот указатель должен обновляться после каждой операции, добавляя лишь постоянные накладные расходы по временной сложности.

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

идти [ править ]

Чтобы объединить две косые биномиальные кучи, сначала удалите все повторяющиеся деревья ранга в каждой куче, выполнив простые связи . Затем объедините кучи так же, как обычные биномиальные кучи, что похоже на двоичное сложение. Деревья с одинаковыми рангами связываются простой ссылкой , и при необходимости дерево переноса передается вверх. Поскольку ранг деревьев в каждой куче теперь уникален, рассматриваются не более трех деревьев одного ранга, что достаточно для установления $O(\log n)$ граница.

пусть   запись   уникально   =   функция    |   t1   ::   t2   ::   ts   , когда   ранг   t1   =   ранг   t2   ->      уникальный   (  simple_link   t1   t2   ::   ts  )    |   ts   ->   ts  let   Rec   merge_uniq   h1   h2   =   сопоставить   h1  ,   h2   с    |   h1  ,   []   ->   h1    |   []  ,   h2   ->   h2    |   t1   ::   ts1  ,   t2   ::   ts2   ->      если   ранг   t1   <   ранг   t2   , то        t1   ::   merge_uniq   ts1   h2      else,   если   ранг   t1   >   ранг   t2   , то        t2   ::   merge_uniq   h1   ts2      else        unique   (  simple_link   t1   t2   ::   merge_uniq   ts1   ts2  )    пусть   объединит   h1   h2   =   merge_uniq   (  уникальный   h1  )   (  уникальный   h2  )

Вставить [ править ]

Создайте косое биномиальное дерево ранга 0 (одноэлементный узел), содержащее вставляемый ключ. Затем рассматриваются два самых маленьких дерева в куче:

Если они оба имеют ранг $r$ , затем выполните косую связь с этими двумя деревьями и одноэлементным узлом. Полученное дерево имеет ранг $r+1$ . Поскольку мог быть только один ранг $r+1$ дерево в исходной куче, инвариант сохраняется.
Если они имеют разные ранги, просто добавьте дерево ранга 0 в начало списка корней. Поскольку список корней ранее не имел повторяющихся деревьев ранга, инвариант не нарушается, так как после него будет не более двух деревьев ранга 0.

Поскольку выполняется до одной ссылки, эта операция выполняется в худшем случае. $O(1)$ время, улучшая биномиальную кучу, которая опирается на амортизированный анализ для своего $O(1)$ связанный, с наихудшим случаем $O(\log n)$ .

позвольте   вставить   k   =   функция    |   t2   ::   t3   ::   ts   , когда   ранг   t2   =   ранг   t3   ->   skew_link   k   t2   t3   ::   ts    |   ts   ->   Дерево   (  k  ,   0  ,   []  )   ::   ts

Удалить-мин [ изменить ]

Найдите и отбросьте узел, содержащий минимальный ключ. Этот узел должен быть корнем дерева. может быть более двух дочерних элементов с рангом 0 Разделите его дочерние элементы на две группы: группы с рангом 0 и группы с рангом > 0. Обратите внимание, что из-за перекоса связей . Дочерние элементы, ранг которых > 0, образуют действительную косую биномиальную кучу, поскольку они уже упорядочены и не имеют дубликатов. Объединение этих детей в кучу занимает $O(\log n)$ время. После этого повторно вставьте в кучу каждого дочернего элемента ранга 0 по цене $O(1)$ каждый. Общее время, необходимое для $O(\log n)$ .

Клавиша уменьшения [ править ]

Эта операция не отличается от биномиальных куч. Уменьшение ключа узла может привести к тому, что он станет меньше своего родителя. Неоднократно обменивайте его с родительским элементом до тех пор, пока не будет удовлетворено свойство минимальной кучи , затрачивая $O(\log n)$ временная сложность. Для этой операции требуется указатель на узел, содержащий рассматриваемый ключ, и ее проще всего выполнить в императивной настройке.

Оптимизации [ править ]

Бродал и Окасаки показали, как можно сократить временную сложность операции слияния до $O(1)$ , применив технику «бутстреппинга» Буксбаума и Тарьяна . ^[2]

Пусть тип примитивной косой биномиальной кучи, содержащей элементы типа $\alpha$ быть $H_{\alpha }$ . Вместо представления леса деревьев, описанного выше, мы поддерживаем одно дерево с глобальным корнем как минимум.

Пусть тип корневой косой биномиальной кучи будет

R_{\alpha }=\alpha \times H_{R_{\alpha }}

,

то есть пара, содержащая элемент типа $\alpha$ и примитивная куча корневых куч.

Наконец, мы определяем тип самозагруженной кучи , заключая корневые кучи в параметр type :

B_{\alpha }=\{\mathrm {Empty} \}+R_{\alpha }

что допускает пустую кучу.

Операции над этой самозагруженной кучей переопределяются соответствующим образом. В следующем коде OCaml простой символ ' обозначает операции для самозагруженных куч.

введите   '  загруженный     =    |   Пусто    |   Корень   укорененного   '  find_min   '  let   '   (  Root   (  k  ,   h  ))   =   k  let   merge   bh1   bh2   =   сопоставить   bh1  ,   bh2   с    |   _,   Пусто   ->   bh1    |   Пусто  ,   _   ->   bh2    |   Root   (  k1  ,   h1  ),   Root   (  k2  ,   h2  )   ->      если   k1   <=   k2   , то        Root   (  k1  ,   вставьте   bh2   h1  )      else        Root   (  k2  ,   вставьте   bh1   h2  )  let   Insert'   k   h   =   merge'   (  Root  (  k  ,   []  ))   h  let   delete_min'   (  Root   (  x  ,   h  ))   =    let   Root   (  y  ,   h1  )   =   find_min   h   in    let   h2   =   delete_min   h   in    Root   (  y  ,   merge   h1   h2  )

Новая операция слияния использует только операции вставки в примитивные кучи. Таким образом, он выполняется в $O(1)$ время. Этот метод можно применить к любой приоритетной очереди с вставкой постоянного времени и логарифмическим слиянием.

Сводка времени работы [ править ]

Вот временные сложности ^[3] различных структур данных кучи. Имена функций предполагают минимальную кучу. Значение « O ( f )» и « Θ ( f )» см в обозначении Big O. .

Операция	найти-мин	удаление-мин	вставлять	клавиша уменьшения	сливаться
Двоичный ^[3]	я (1)	Θ (логарифм n )	О (логарифм n )	О (логарифм n )	Θ ( н )
Левый	я (1)	Θ (логарифм n )	Θ (логарифм n )	О (логарифм n )	Θ (логарифм n )
Биномиальный ^[3]^[4]	я (1)	Θ (логарифм n )	я (1) ^[а]	Θ (логарифм n )	О (логарифм n )
Наклонный бином ^[5]	я (1)	Θ (логарифм n )	я (1)	Θ (логарифм n )	О (логарифм n ) ^[б]
Сопряжение ^[6]	я (1)	О (логарифм n ) ^[а]	я (1)	о (логарифм n ) ^[а]^[с]	я (1)
Сопряжение по рангам ^[9]	я (1)	О (логарифм n ) ^[а]	я (1)	я (1) ^[а]	я (1)
Фибоначчи ^[3]^[10]	я (1)	О (логарифм n ) ^[а]	я (1)	я (1) ^[а]	я (1)
Строгий Фибоначчи ^[11]	я (1)	О (логарифм n )	я (1)	я (1)	я (1)
Мостовая долина ^[12]^[д]	я (1)	О (логарифм n )	я (1)	я (1)	я (1)
2–3 кучи ^[14]	я (1)	О (логарифм n ) ^[а]	я (1) ^[а]	я (1)	О (логарифм n )

^ Jump up to: ^а ^б ^с ^д ^и ^ж ^г ^час ^я Амортизированное время.
^ в наихудшем случае Бродал и Окасаки описывают метод уменьшения сложности объединения до Θ (1); этот метод применим к любой структуре данных кучи, которая имеет вставку в Θ (1) и find-min , delete-min , объединение в O (log n ).
^ Нижняя граница $\Omega (\log \log n),$ ^[7] верхняя граница $O(2^{2{\sqrt {\log \log n}}}).$ ^[8]
^ Бродал и Окасаки позже описывают постоянный вариант с теми же границами, за исключением клавиши уменьшения, которая не поддерживается.Кучи с n элементами могут быть построены снизу вверх за O ( n ). ^[13]

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

^ Бродал, Герт Столтинг; Окасаки, Крис (ноябрь 1996 г.), «Оптимальные чисто функциональные очереди приоритетов», Journal of Functional Programming , 6 (6): 839–857, doi : 10.1017/s095679680000201x
^ Бухсбаум, Алабама; Тарьян, Р.Э. (май 1995 г.). «Конфлюэнтно сохраняемые деки посредством структурной начальной загрузки данных» . Журнал алгоритмов . 18 (3): 513–547. дои : 10.1006/jagm.1995.1020 . ISSN 0196-6774 .
^ Jump up to: ^а ^б ^с ^д Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л. (1990). Введение в алгоритмы (1-е изд.). MIT Press и McGraw-Hill. ISBN 0-262-03141-8 .
^ «Биномиальная куча | Блестящая вики по математике и естественным наукам» . блестящий.орг . Проверено 30 сентября 2019 г.
^ Бродал, Герт Столтинг; Окасаки, Крис (ноябрь 1996 г.), «Оптимальные чисто функциональные очереди приоритетов», Journal of Functional Programming , 6 (6): 839–857, doi : 10.1017/s095679680000201x
^ Яконо, Джон (2000), «Улучшенные верхние границы для спаривания куч», Proc. 7-й скандинавский семинар по теории алгоритмов (PDF) , Конспекты лекций по информатике, том. 1851, Springer-Verlag, стр. 63–77, arXiv : 1110.4428 , CiteSeerX 10.1.1.748.7812 , doi : 10.1007/3-540-44985-X_5 , ISBN 3-540-67690-2
^ Фредман, Майкл Лоуренс (июль 1999 г.). «Об эффективности объединения куч и связанных структур данных» (PDF) . Журнал Ассоциации вычислительной техники . 46 (4): 473–501. дои : 10.1145/320211.320214 .
^ Петти, Сет (2005). К окончательному анализу парных куч (PDF) . FOCS '05 Материалы 46-го ежегодного симпозиума IEEE по основам информатики. стр. 174–183. CiteSeerX 10.1.1.549.471 . дои : 10.1109/SFCS.2005.75 . ISBN 0-7695-2468-0 .
^ Хёплер, Бернхард; Сен, Сиддхартха; Тарьян, Роберт Э. (ноябрь 2011 г.). «Кучи ранговых пар» (PDF) . СИАМ Дж. Компьютерные технологии . 40 (6): 1463–1485. дои : 10.1137/100785351 .
^ Фредман, Майкл Лоуренс ; Тарьян, Роберт Э. (июль 1987 г.). «Кучи Фибоначчи и их использование в улучшенных алгоритмах оптимизации сети» (PDF) . Журнал Ассоциации вычислительной техники . 34 (3): 596–615. CiteSeerX 10.1.1.309.8927 . дои : 10.1145/28869.28874 .
^ Бродал, Герт Столтинг ; Лагояннис, Джордж; Тарьян, Роберт Э. (2012). Строгие кучи Фибоначчи (PDF) . Материалы 44-го симпозиума по теории вычислений - STOC '12. стр. 1177–1184. CiteSeerX 10.1.1.233.1740 . дои : 10.1145/2213977.2214082 . ISBN 978-1-4503-1245-5 .
^ Бродал, Герт С. (1996), «Эффективные приоритетные очереди для наихудшего случая» (PDF) , Proc. 7-й ежегодный симпозиум ACM-SIAM по дискретным алгоритмам , стр. 52–58.
^ Гудрич, Майкл Т .; Тамассия, Роберто (2004). «7.3.6. Построение кучи снизу вверх». Структуры данных и алгоритмы в Java (3-е изд.). стр. 338–341. ISBN 0-471-46983-1 .
^ Такаока, Тадао (1999), Теория 2–3 куч (PDF) , стр. 12

[amortized-5] Jump up to: ^а ^б ^с ^д ^и ^ж ^г ^час ^я Амортизированное время.

[7] в наихудшем случае Бродал и Окасаки описывают метод уменьшения сложности объединения до Θ (1); этот метод применим к любой структуре данных кучи, которая имеет вставку в Θ (1) и find-min , delete-min , объединение в O (log n ).

[pairingdecreasekey-11] Нижняя граница $\Omega (\log \log n),$ ^[7] верхняя граница $O(2^{2{\sqrt {\log \log n}}}).$ ^[8]

[brodal-17] Бродал и Окасаки позже описывают постоянный вариант с теми же границами, за исключением клавиши уменьшения, которая не поддерживается.Кучи с n элементами могут быть построены снизу вверх за O ( n ). ^[13]

[1] Бродал, Герт Столтинг; Окасаки, Крис (ноябрь 1996 г.), «Оптимальные чисто функциональные очереди приоритетов», Journal of Functional Programming , 6 (6): 839–857, doi : 10.1017/s095679680000201x

[2] Бухсбаум, Алабама; Тарьян, Р.Э. (май 1995 г.). «Конфлюэнтно сохраняемые деки посредством структурной начальной загрузки данных» . Журнал алгоритмов . 18 (3): 513–547. дои : 10.1006/jagm.1995.1020 . ISSN 0196-6774 .

[CLRS-3] Jump up to: ^а ^б ^с ^д Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л. (1990). Введение в алгоритмы (1-е изд.). MIT Press и McGraw-Hill. ISBN 0-262-03141-8 .

[4] «Биномиальная куча | Блестящая вики по математике и естественным наукам» . блестящий.орг . Проверено 30 сентября 2019 г.

[6] Бродал, Герт Столтинг; Окасаки, Крис (ноябрь 1996 г.), «Оптимальные чисто функциональные очереди приоритетов», Journal of Functional Programming , 6 (6): 839–857, doi : 10.1017/s095679680000201x

[Iacono-8] Яконо, Джон (2000), «Улучшенные верхние границы для спаривания куч», Proc. 7-й скандинавский семинар по теории алгоритмов (PDF) , Конспекты лекций по информатике, том. 1851, Springer-Verlag, стр. 63–77, arXiv : 1110.4428 , CiteSeerX 10.1.1.748.7812 , doi : 10.1007/3-540-44985-X_5 , ISBN 3-540-67690-2

[Fredman1999-9] Фредман, Майкл Лоуренс (июль 1999 г.). «Об эффективности объединения куч и связанных структур данных» (PDF) . Журнал Ассоциации вычислительной техники . 46 (4): 473–501. дои : 10.1145/320211.320214 .

[10] Петти, Сет (2005). К окончательному анализу парных куч (PDF) . FOCS '05 Материалы 46-го ежегодного симпозиума IEEE по основам информатики. стр. 174–183. CiteSeerX 10.1.1.549.471 . дои : 10.1109/SFCS.2005.75 . ISBN 0-7695-2468-0 .

[12] Хёплер, Бернхард; Сен, Сиддхартха; Тарьян, Роберт Э. (ноябрь 2011 г.). «Кучи ранговых пар» (PDF) . СИАМ Дж. Компьютерные технологии . 40 (6): 1463–1485. дои : 10.1137/100785351 .

[Fredman_And_Tarjan-13] Фредман, Майкл Лоуренс ; Тарьян, Роберт Э. (июль 1987 г.). «Кучи Фибоначчи и их использование в улучшенных алгоритмах оптимизации сети» (PDF) . Журнал Ассоциации вычислительной техники . 34 (3): 596–615. CiteSeerX 10.1.1.309.8927 . дои : 10.1145/28869.28874 .

[14] Бродал, Герт Столтинг ; Лагояннис, Джордж; Тарьян, Роберт Э. (2012). Строгие кучи Фибоначчи (PDF) . Материалы 44-го симпозиума по теории вычислений - STOC '12. стр. 1177–1184. CiteSeerX 10.1.1.233.1740 . дои : 10.1145/2213977.2214082 . ISBN 978-1-4503-1245-5 .

[15] Бродал, Герт С. (1996), «Эффективные приоритетные очереди для наихудшего случая» (PDF) , Proc. 7-й ежегодный симпозиум ACM-SIAM по дискретным алгоритмам , стр. 52–58.

[16] Гудрич, Майкл Т .; Тамассия, Роберто (2004). «7.3.6. Построение кучи снизу вверх». Структуры данных и алгоритмы в Java (3-е изд.). стр. 338–341. ISBN 0-471-46983-1 .

[18] Такаока, Тадао (1999), Теория 2–3 куч (PDF) , стр. 12

[1]

[2]

[3]

[4]

[а]

[5]

[б]

[6]

[с]

[9]

[10]

[11]

[12]

[д]

[14]

[7]

[8]

[13]