Алгоритмы слияния двух куч

Question

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

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

Answer 1

Это решит проблему и даст вам правильную кучу - но это не будет эффективно.

Создание [двоичной] кучи n элементов с нуля равно O(n), в то время как объединение 2 существующих биномиальных куч представляет собой O(logn).

Answer 2

Если вы подумаете об этом, создание одной кучи путем отбрасывания всей информации, встроенной в порядок других кучи, не может быть оптимальным.В худшем случае, вы должны добавить все элементы в куче 2 в кучу 1, и это будет только половина работы по созданию новой кучи с нуля.

Но на самом деле вы можете сделать путь лучше, чем это.Объединение двух правильно сформированных куч требует немного больше, чем нахождение точки вставки для одного из корней в дереве другой кучи и вставка ее в этой точке.Никакой дальнейшей работы не требуется, и вы проделали не более ln N работы!См. здесь для подробного алгоритма.

Answer 3

Очереди Brodal и очереди Brodal-Okasaki (загруженные косые биномиальные кучи) дают наилучшие асимптотические границы в худшем случае для объединенных куч, поддерживая O (1) вставки, слияние и findMin и O (log n) deleteMin. Очереди Brodal эфемерны и поддерживают эффективное удаление и уменьшение ключа. Очереди Brodal-Okasaki являются устойчиво устойчивыми (на самом деле чисто функциональными), но не поддерживают удаление или уменьшение ключа. К сожалению, Бродал и Окасаки говорят, что обе эти реализации неэффективны на практике, и Бродал считает, что его очереди слишком сложны, чтобы быть практичными в любом случае.

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

Answer 4

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

повторяйте шаги с 1 по 4, пока одна из куч не станет пустой

1. Если головы (которые являются биномиальными деревьями) в двух кучах имеют одинаковую степень, тогда вы назначаете голову кучи с большим ключом, как дочерний элемент потомка головы кучи с меньшим ключом. Соответственно, степень головы последней кучи будет увеличена на 1, и голова первой кучи станет следующим элементом ее текущей головы и перейдите к шагу 2, если они другой степени, затем перейдите к шагу 4 * 1007. *

2. Если головка и следующее биномиальное дерево в последней куче на шаге 1 имеют одинаковую степень, то перейдите к шагу 3, иначе перейдите к шагу 1

3. Объедините голову и ее следующий элемент в куче так же, как вы это делали в шаге 1, и назначьте новое комбинированное биномиальное дерево в качестве головы и перейдите к шагу 2.

4. Посмотрите, какая из двух куч имеет голову с более низкой степенью. Назначьте головку этой кучи главой другой кучи и удалите ее из кучи, где она изначально присутствовала