Максимальная глубина кучи мин - PullRequest
Новая
       16

Максимальная глубина кучи мин

0 голосов
/ 29 февраля 2020

Рассмотрим минимальную кучу, содержащую все целые числа от 1 до 1023 ровно один раз. Если root находится на глубине 0, максимальная глубина, на которой может появиться 9, равна? Ответ на вопрос: 8.

Но, учитывая, что min heap - это почти полная BT с -

1) для d <- 0 до h-1, все уровни имеют 2 ^ d узлов. </p>

2) для d <- h, узлов заполнены слева. </p>

Источник: http://homepages.math.uic.edu/~leon/cs-mcs401-s08/handouts/nearly_complete.pdf

Какая ошибка в ответе - 4, поскольку обход уровня порядка будет { 1,2 3,4 5 6,7 8 9 ...}

1 Ответ

0 голосов
/ 29 февраля 2020

В min-heap требуется поместить элементы, которые больше, чем их родительский узел.

Учитывая этот вопрос, можно указать 1 как root, затем 2 как его левого потомка и любой элемент больше 9 (скажем, 512) как его правый ребенок. Для 2 можно продолжить таким образом, указав 3 как левого ребенка и, скажем, 513 как его правого ребенка. Последняя полученная минимальная куча будет - 

                   1
                  / \
                 /   \
                2     512
               / \      /\
              /   \    /  \
             3   513  514  515
            /\    /\   /\   /\
           /  \  
          4  516  .  .  .  .  .  . 
         /   / \ /\  /\ /\ /\ /\ /\
        5   .  . ..  .. .. .. .. ...
       /   /\ /\ /\/\
      6   . . . . ........................... 
     /
    7 .......................................................
   /   
  8 ......................................................
 /
9

Точки обозначают заполненные уровни и могут быть заменены элементами из [517 758], так как уровни должны быть заполнены.

Глубина 9 это 8

...