Макс и Мин куча с одинаковыми элементами

Рассмотрим следующий пример. Я добавляю случайные числа к минимальной куче и в то же время добавляю одинаковые числа в том же порядке к максимальной куче. Таким образом, в конце эти 2 кучи будут иметь одинаковые числа, с разницей один будет минимальной кучей, а вторая — максимальной кучей.

Теперь вот вопрос:

Если я решу удалить максимальный элемент из максимальной кучи, будет ли этот максимальный элемент из максимальной кучи всегда находиться в нижней части минимальной кучи? Если нет, то другой вопрос заключается в том, что если я хочу удалить этот элемент max из минимальной кучи, поменяв его местами с последним элементом минимальной кучи, удалив последний элемент, нужно ли мне когда-либо запускать операцию, которая будет сравнивать этот переключаемый элемент со своим ребенком, чтобы починить мин кучу? Или это всегда будет иметь место, чтобы сравнить его с родителем, чтобы исправить мин кучи?

2

Решение

По определению максимальной кучи, корень всегда больше, чем его дети. Однако среди детей нет определенного порядка, поэтому левый ребенок не всегда больше правого и наоборот. Элемент max в куче max, который является корнем, должен находиться на листе в куче min. Мы не знаем, какой лист, это будет зависеть от конфигурации элементов. (т.е. порядок, в котором эти элементы вставлены, потому что обычно элементы вставляются для заполнения от крайней левой до правой стороны дерева)

3

Другие решения

Других решений пока нет …

По вопросам рекламы [email protected]