Должно ли двоичное дерево кучи завершаться, чтобы быть кучей?

Question

У меня есть небольшая путаница с кучами в c ++, и я хочу лучше понять это.

Должно ли двоичное дерево быть полным (полное двоичное дерево), чтобы его можно было классифицировать как кучу?

Должна ли куча быть полным двоичным деревом?Ответ профессора - нет, но я не проверял профессора.

Определение кучи состояния сетевых ресурсов состоит в том, что они должны быть полными двоичными деревьями.Мой профессор утверждает, что куча - это двоичное дерево с двумя особыми свойствами.

Answer 1

Я полагаю, что вас особенно беспокоит двоичная куча.

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

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