Если у меня есть двоичная максимальная куча (почти полное двоичное дерево со свойством максимальной кучи), то всегда ли медиана будет конечным узлом? Я нашел несколько примеров, когда это так, но не нашел контрпримера, хотя пока этого мне недостаточно, чтобы формально доказать это.
то есть для набора значений {1,2,3,4,5}, где медиана равна [3], дерево будет таким:
5
/ \
4 [3]
/ \
2 1
Таким образом, в этом случае медиана является конечным узлом.
Нет, это не всегда листовой узел. Вы можете легко изменить свой пример, чтобы доказать это. Другая допустимая максимальная куча, использующая те же элементы:
5
/ \
[3] 4
/ \
2 1
Рассмотрим полную максимальную кучу из 7 элементов:
7
6 [4]
1 5 3 2
Это допустимая максимальная куча. Самый большой элемент находится в корне, а все дочерние узлы меньше своих родителей.
Из этих двух примеров должно быть ясно, что нельзя предполагать, что медиана в куче всегда является конечным узлом.
