В максимальной куче H из n элементов верхние 2 элемента powerk -1 находятся на первых k уровнях. Как доказать это как ложное?

Question

Докажите приведенное выше утверждение как false.

n и k являются натуральными числами, так что 2 powerk -1 <= n. </p>

В максимальной куче из n элементов верхние 2 элемента powerk -1в первых k уровнях.

Answer 1

Я думаю, что вы имеете в виду:

Верхние 2 ^k-1 элементы находятся на верхних k уровнях.

Мы можем доказать это противоречием. Здесь максимальная куча из 15 предметов.

         F
       /   \
     E       7
    / \     / \
   D   A   6   5
  / \ / \ / \ / \ 
  C B 9 8 4 3 2 1

Это допустимая куча. Каждый элемент меньше своего родителя.

Итак, давайте предположим, что ваше утверждение верно, что верхние 2 ^k-1 элементы находятся на верхних k уровнях. Таким образом, верхние 4 (2 ^3-1 ) элемента должны находиться на верхних 3 уровнях. В этом случае это будут F, E, D и C. Но C находится на 4-м уровне. Это противоречит утверждению.

Или вы имеете в виду, что верхние 2 ^k -1 предметов должны находиться на верхних k уровнях? В этом случае верхние 3 (2 ² -1) должны находиться в верхних 2 уровнях. Но опять же, пункт D, который является третьим по величине, находится на 3-м уровне. Опять же, это противоречит утверждению.