ЧЕРТЕЖ Биномиальная куча

Кто-нибудь знает, как нарисовать биномиальную максимальную кучу для значений 1-10? В настоящее время я изучаю кучи в своем курсе «Структура данных», но после просмотра нескольких видео я все еще не могу этого понять! И я не уверен, правильно ли я поступаю.

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

Вот моя реализация (каждый "возврат" - это новый уровень

10

9 8 6 (все 3 числа связаны с 10)

7 5 4 (7 соединяется с 8, 5 и 4 соединяется с 6)

2 1 3 (2 соединены с 7, 1 с 5, 3 с 4)

Я не знал, куда поставить 1 и 2.

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


person webdesignnoob    schedule 05.03.2020    source источник


Ответы (1)


Согласно информации тега, биномиальная куча — это лес биномиальных деревьев. И, согласно этой статье в Википедии, количество элементов в каждом дереве всегда должно быть степенью 2. Кроме того, может быть только одно дерево каждого размера. Так, например, если есть два дерева размера 4, то их нужно объединить в одно дерево размера 8.

Таким образом, биномиальная куча с 10 элементами состоит из двух деревьев: дерева с 8 элементами и дерева с 2 элементами. Это означает, что ваша куча выглядит так, как показано ниже. 1 и 2 не связаны с другими восемью элементами. Они находятся в отдельном дереве.

введите здесь описание изображения

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

person user3386109    schedule 05.03.2020
comment
Ах, два отдельных дерева имеют гораздо больше смысла, чем то, о чем я думал. Большое спасибо! :) - person webdesignnoob; 06.03.2020