Массив, который является максимальной кучей, но чья обратная сторона не является минимальной кучей?

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

Создайте массив с 5 элементами, который является максимальной кучей, но чья обратная сторона не является минимальной кучей.

A = [ 100, 50, 49, 40, 41 ]

    100
  |     |
  50     49
 |  |
40  41

Итак, просто проверяем, что если я прочитаю это дерево как минимальную кучу, я прочитаю 40, 41, 50, 49, 100? Спасибо - это смущает меня, и любое понимание кучи было бы потрясающим!


arrays data-structures heapsort
person Megan Byers    schedule 15.03.2018    source источник

Ответы (1)


arrow_upward
2
arrow_downward

Простой контрпример:
Рассмотрим A = [10 7 3 6 5] - допустимый массив max-heap.

     10
   |     |
  7      3
 |  |
 6  5

Но обратный B = [5 6 3 7 10] не является минимальной кучей

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

person MBo    schedule 15.03.2018