Биномиальная куча

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

В информатике биномиальная куча — это структура данных , действующая как приоритетная очередь . Это пример объединяемой кучи (также называемой объединяемой кучей), поскольку он поддерживает объединение двух куч за логарифмическое время. Он реализован как куча, аналогичная двоичной куче , но с использованием специальной древовидной структуры, которая отличается от полных двоичных деревьев, используемых в двоичных кучах. ^[1] Биномиальные кучи были изобретены в 1978 году Жаном Вюлеменом . ^[1]^[2]

Биномиальная куча [ править ]

Биномиальная куча реализована как набор биномиальных деревьев (сравните с бинарной кучей , которая имеет форму одного бинарного дерева ), которые рекурсивно определяются следующим образом: ^[1]

Биномиальное дерево порядка 0 представляет собой один узел
Биномиальное дерево порядка $k$ имеет корневой узел, дочерние элементы которого являются корнями биномиальных деревьев порядков $k-1$ , $k-2$ , ..., 2, 1, 0 (в таком порядке).

Биномиальное дерево порядка $k$ имеет $2^{k}$ узлы и высота $k$ . Название происходит от формы: биномиальное дерево порядка. $k$ имеет ${\tbinom {k}{d}}$ узлы на глубине $d$ , биномиальный коэффициент . В силу своей структуры биномиальное дерево порядка $k$ можно построить из двух деревьев порядка $k-1$ присоединив один из них как самый левый дочерний элемент корня другого дерева. Эта функция является центральной в операции слияния биномиальной кучи, что является ее основным преимуществом перед другими обычными кучами. ^[1]^[3]

Структура биномиальной кучи [ править ]

Биномиальная куча реализуется как набор биномиальных деревьев, удовлетворяющих свойствам биномиальной кучи : ^[1]

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

Первое свойство гарантирует, что корень каждого биномиального дерева содержит наименьший ключ в дереве. Отсюда следует, что самый маленький ключ во всей куче является одним из корней. ^[1]

Второе свойство означает, что биномиальная куча с $n$ узлов состоит не более чем из $1+\log _{2}n$ биномиальные деревья, где $\log _{2}$ это двоичный логарифм . Количество и порядок этих деревьев однозначно определяются количеством узлов. $n$ : существует одно биномиальное дерево для каждого ненулевого бита в двоичном представлении числа. $n$ . Например, десятичное число 13 в двоичном формате равно 1101. $2^{3}+2^{2}+2^{0}$ , и, таким образом, биномиальная куча с 13 узлами будет состоять из трех биномиальных деревьев порядков 3, 2 и 0 (см. рисунок ниже). ^[1]^[3]

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

Количество различных способов, которыми $n$ элементы с разными ключами могут быть организованы в биномиальную кучу, равную наибольшему нечетному делителю $n!$ . Для $n=1,2,3,\dots$ эти цифры

1, 1, 3, 3, 15, 45, 315, 315, 2835, 14175, ... (последовательность A049606 в OEIS )

Если $n$ элементы вставляются в биномиальную кучу в равномерно случайном порядке, каждое из этих расположений одинаково вероятно. ^[3]

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

Поскольку ни одна операция не требует произвольного доступа к корневым узлам биномиальных деревьев, корни биномиальных деревьев могут храниться в связанном списке , упорядоченном по возрастанию порядка дерева. Поскольку количество дочерних элементов для каждого узла является переменным, для каждого узла нецелесообразно иметь отдельные ссылки на каждого из своих дочерних элементов, как это обычно бывает в двоичном дереве ; вместо этого можно реализовать это дерево, используя ссылки от каждого узла к его дочернему элементу высшего порядка в дереве и к его брату следующего меньшего порядка, чем он. Эти одноуровневые указатели можно интерпретировать как следующие указатели в связанном списке дочерних элементов каждого узла, но в порядке, противоположном связанному списку корней: от наибольшего к наименьшему порядку, а не наоборот. Это представление позволяет связать вместе два дерева одного и того же порядка, образуя дерево следующего большего порядка за постоянное время. ^[1]^[3]

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

Операция слияния двух куч используется как подпрограмма в большинстве других операций. Базовая подпрограмма этой процедуры объединяет пары биномиальных деревьев одного и того же порядка. Это можно сделать путем сравнения ключей в корнях двух деревьев (наименьшие ключи в обоих деревьях). Корневой узел с большим ключом становится дочерним по отношению к корневому узлу с меньшим ключом, увеличивая его порядок на единицу: ^[1]^[3]

function mergeTree(p, q)
    if p.root.key <= q.root.key
        return p.addSubTree(q)
    else
        return q.addSubTree(p)

В более общем смысле, чтобы объединить две кучи, списки корней обеих куч просматриваются одновременно аналогично алгоритму слияния . в последовательности от меньших порядков деревьев к более крупным. Когда только одна из двух объединяемых куч содержит дерево порядка $j$ , это дерево перемещается в выходную кучу. Когда обе кучи содержат дерево порядка $j$ , два дерева объединяются в одно дерево порядка $j+1$ так что свойство минимальной кучи удовлетворяется. Позже может возникнуть необходимость объединить это дерево с каким-либо другим деревом порядка. $j+1$ в одной из двух входных куч. В ходе работы алгоритм проверит не более трех деревьев любого порядка: два из двух объединенных куч и одно, состоящее из двух деревьев меньшего размера. ^[1]^[3]

function merge(p, q)
    while not (p.end() and q.end())
        tree = mergeTree(p.currentTree(), q.currentTree())

        if not heap.currentTree().empty()
            tree = mergeTree(tree, heap.currentTree())

        heap.addTree(tree)
        heap.next(); p.next(); q.next()

Поскольку каждое биномиальное дерево в биномиальной куче соответствует биту в двоичном представлении его размера, существует аналогия между слиянием двух куч и двоичным сложением размеров двух куч справа налево. Всякий раз, когда во время сложения происходит перенос, это соответствует слиянию двух биномиальных деревьев во время слияния. ^[1]^[3]

Обход каждого биномиального дерева во время слияния включает только корни, поэтому затрачиваемое время не превышает порядка. $\log _{2}n$ и, следовательно, время работы $O(\log n)$ . ^[1]^[3]

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

Вставку нового элемента в кучу можно выполнить, просто создав новую кучу, содержащую только этот элемент, а затем объединив ее с исходной кучей. Из-за слияния одна вставка занимает время. $O(\log n)$ . Однако это можно ускорить с помощью процедуры слияния, которая сокращает слияние после того, как оно достигает точки, в которой только одна из объединенных куч имеет деревья большего порядка. Благодаря этому ускорению в ряде $k$ последовательные вставки, общее время вставок равно $O(k+\log n)$ . Другой способ выразить это так: (после логарифмических затрат на первую вставку в последовательность) каждая вставка имеет амортизированное время последующая $O(1)$ (т.е. константа) на каждую вставку. ^[1]^[3]

Вариант биномиальной кучи, косая биномиальная куча , обеспечивает постоянное время вставки в худшем случае за счет использования лесов, размеры деревьев которых основаны на асимметричной двоичной системе счисления, а не на двоичной системе счисления. ^[4]

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

Чтобы найти минимальный элемент кучи, найдите минимум среди корней биномиальных деревьев. Это можно сделать в $O(\log n)$ время, так как есть только $O(\log n)$ корни деревьев для осмотра. ^[1]

Используя указатель на биномиальное дерево, содержащее минимальный элемент, время этой операции можно сократить до $O(1)$ . Указатель должен обновляться при выполнении любой операции, кроме поиска минимума. Это можно сделать в $O(\log n)$ время каждого обновления без увеличения общего асимптотического времени выполнения какой-либо операции. ^{[ нужна ссылка ]}

Удалить минимум [ править ]

Чтобы удалить минимальный элемент из кучи, сначала найдите этот элемент, удалите его из корня его биномиального дерева и получите список его дочерних поддеревьев (каждое из которых является биномиальными деревьями разных порядков). Преобразуйте этот список поддеревьев в отдельную биномиальную кучу, изменив их порядок от наименьшего к наибольшему. Затем объедините эту кучу с исходной кучей. Поскольку каждый корень имеет не более $\log _{2}n$ дети, создание этой новой кучи требует времени $O(\log n)$ . Объединение куч требует времени $O(\log n)$ , поэтому вся операция удаления минимума занимает время $O(\log n)$ . ^[1]

function deleteMin(heap)
    min = heap.trees().first()
    for each current in heap.trees()
        if current.root < min.root then min = current
    for each tree in min.subTrees()
        tmp.addTree(tree)
    heap.removeTree(min)
    merge(heap, tmp)

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

После уменьшения ключа элемента он может стать меньше ключа его родителя, что нарушает свойство минимальной кучи. В этом случае замените элемент его родителем и, возможно, также его прародителем и т. д., пока свойство минимальной кучи больше не будет нарушено. Каждое биномиальное дерево имеет высоту не более $\log _{2}n$ , так что это занимает $O(\log n)$ время. ^[1] Однако эта операция требует, чтобы представление дерева включало указатели от каждого узла на его родительский элемент в дереве, что несколько усложняет реализацию других операций. ^[3]

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

Чтобы удалить элемент из кучи, уменьшите его ключ до отрицательной бесконечности (или, что то же самое, до некоторого значения, меньшего, чем любой элемент в куче), а затем удалите минимум в куче. ^[1]

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

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

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

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

Приложения [ править ]

См. также [ править ]

Слабая куча — комбинация структур данных двоичной и биномиальной кучи.

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

^ Jump up to: Перейти обратно: ^а ^б ^с ^д ^и ^ж ^г ^час ^я ^дж ^к ^л ^м ^н ^тот ^п ^д Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л .; Штейн, Клиффорд (2001) [1990]. «Глава 19: Биномиальные кучи». Введение в алгоритмы (2-е изд.). MIT Press и McGraw-Hill. стр. 455–475. ISBN 0-262-03293-7 .
^ Виймен, Жан (1 апреля 1978 г.). «Структура данных для управления приоритетными очередями» . Коммуникации АКМ . 21 (4): 309–315. дои : 10.1145/359460.359478 .
^ Jump up to: Перейти обратно: ^а ^б ^с ^д ^и ^ж ^г ^час ^я ^дж Браун, Марк Р. (1978). «Реализация и анализ алгоритмов биномиальной очереди». SIAM Journal по вычислительной технике . 7 (3): 298–319. дои : 10.1137/0207026 . МР 0483830 .
^ Бродал, Герт Столтинг; Окасаки, Крис (ноябрь 1996 г.), «Оптимальные чисто функциональные очереди приоритетов», Journal of Functional Programming , 6 (6): 839–857, doi : 10.1017/s095679680000201x
^ 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

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

Две реализации биномиальной кучи на языке C (общая и оптимизированная для целочисленных ключей)
Реализация биномиальной кучи на Haskell
Общая реализация биномиальной кучи на Lisp

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

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

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

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

[clrs-1] Jump up to: Перейти обратно: ^а ^б ^с ^д ^и ^ж ^г ^час ^я ^дж ^к ^л ^м ^н ^тот ^п ^д Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л .; Штейн, Клиффорд (2001) [1990]. «Глава 19: Биномиальные кучи». Введение в алгоритмы (2-е изд.). MIT Press и McGraw-Hill. стр. 455–475. ISBN 0-262-03293-7 .

[2] Виймен, Жан (1 апреля 1978 г.). «Структура данных для управления приоритетными очередями» . Коммуникации АКМ . 21 (4): 309–315. дои : 10.1145/359460.359478 .

[brown-3] Jump up to: Перейти обратно: ^а ^б ^с ^д ^и ^ж ^г ^час ^я ^дж Браун, Марк Р. (1978). «Реализация и анализ алгоритмов биномиальной очереди». SIAM Journal по вычислительной технике . 7 (3): 298–319. дои : 10.1137/0207026 . МР 0483830 .

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

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

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

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

[Iacono-10] Яконо, Джон (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-11] Фредман, Майкл Лоуренс (июль 1999 г.). «Об эффективности объединения куч и связанных структур данных» (PDF) . Журнал Ассоциации вычислительной техники . 46 (4): 473–501. дои : 10.1145/320211.320214 .

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

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

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

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

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

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

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

[1]

[2]

[3]

[4]

[5]

[6]

[а]

[7]

[б]

[8]

[с]

[11]

[12]

[13]

[14]

[д]

[16]

[9]

[10]

[15]

v т и Структуры данных
Типы	Коллекция Контейнер
Абстрактный	Ассоциативный массив Мультикарта Структура поисковых данных Список Куча Очередь Двусторонняя очередь Приоритетная очередь Двусторонняя приоритетная очередь Набор Мультисет Непересекающееся множество
Массивы	Битовый массив Круговой буфер Динамический массив Хэш-таблица Дерево хешированного массива Разреженная матрица
Связано	Список ассоциаций Связанный список Пропустить список Развернутый связанный список Связанный список XOR
Деревья	B-дерево Бинарное дерево поиска АА-дерево АВЛ-дерево Красно-черное дерево Самобалансирующееся дерево Распространение дерева Куча Двоичная куча Биномиальная куча Куча Фибоначчи R-дерево Р* дерево R+ дерево Гильбертово R-дерево Трие Хэш-дерево
Графики	Бинарная диаграмма решений Ориентированный ациклический граф Направленный ациклический граф слов
Список структур данных