в двоичной максимальной куче, разве родительский узел не больше его дочерних узлов?
Я ошибся в этом вопросе, потому что в вопросе Binary Max Heap говорится: "Если y является узлом в правом поддереве узла x, тогда y.key >= x.key". Прикрепил скриншот вопроса ниже.
Вопрос о максимальном размере двоичной кучи
если y является узлом в поддереве узла x, я думаю, что x.key больше, чем y.key, поскольку в соответствии со свойством максимальной кучи родительский узел больше, чем его дочерние элементы. Я хотел бы знать, не упускаю ли я чего-то. Заранее спасибо.
2 ответа
Куча двоичного максимума - это куча, в которой -
Корневой узел имеет максимальное значение.
Значение каждого узла равно или меньше значения его родительского узла.
является полным двоичным деревом.
В Binary Max-Heap родительский узел всегда больше любого из его дочерних узлов.
Так что ты прав! x.key больше, чем y.key, поскольку в соответствии со свойством max heap родительский узел больше, чем его дочерние элементы.
Не думайте, что вам ничего не хватает. Minheap поднимает минимальный ключ для root, maxheap поднимает максимальный ключ для root.
Теперь, мин-макс куч... те интересны.