Значит ли медианное значение в куче в нижнем ряду?

Question

В классе мы узнали, что двоичная куча имеет n/2 листа, но разве это должно заверить нас, что медиана этой кучи - лист? Или это может быть узел, у которого есть левый/правый ребенок? Кроме того, это зависит от n?

Answer 1

Вот контрпример с помощью чисел 1, 2, 3, 4, 5, 6, 7:

    1 
       4  2 
       5 6 3 7 

Здесь средний показатель равен 4, и это не в нижнем ряду.

Вот еще один пример с 1, 2, 3, ..., 15 (медиана 8)

      1 
       8    2 
      9  10  3  4 
      11 12 13 14  5 6 7 15 

Если у вас есть 2 ^п - 1 общие элементы для п ≥ 3. Вы можете затем постройте двоичную кучу, содержащую все эти элементы, и со срединным элементом (2 ^n-1) во второй строке следующим образом: положите 1 сверху, положите 2 ^n-1 в качестве его левого дочернего элемента и 2 в качестве его правой ребенок. Поместите номер 2 ^н-1 + 1 через 2 ^п - 2, как дети медианы, и поместить число 3 через 2 ^п-1 - 1 и 2 ^п - 1 как дети 2.

Единственный раз, когда это не будет работать, когда у вас есть 1 или 3 элемента, так как с одним элементом медиана является единственным элементом, а это корень и с тремя элементами медиана не может быть корнем и поэтому должна быть в нижнем ряду.

Надеюсь, это поможет!