Двоичная индексация кучи

Question

В курсе алгоритмов Уэйна и Седжвика задается следующий вопрос:

"Предположим, что массив a [] - это максимальная куча, которая содержит различные целочисленные ключи 1,2,…, Nс N≥7. Ключ N должен быть в [1], а ключ N − 1 должен быть либо в [2], либо в [3]. Где должен быть ключ N − 2? "

Правильный ответ: «2, 3, 4, 5, 6 или 7».Я ожидал, что это должно было быть "2 или 3", потому что N-2 должен быть на втором уровне двоичной кучи, а не на третьем ... Может кто-нибудь прояснить это, пожалуйста?Заранее спасибо

Answer 1

В максимальной куче два самых больших элемента - это корневой элемент и самый большой из его дочерних элементов.Третьим по величине является либо дочерний элемент корня, либо дочерний элемент второго по величине.Рассмотрим эти две кучи, где A - наибольший элемент, а G - наименьший:

      A                   A
   B     C             B     D
  D E   F G           C G   F E

В первом третьем по величине элемент является меньшим из двух дочерних элементов корня.Во второй куче третий элемент является потомком второго по величине элемента.Независимо от того, как вы расположите кучу, третий элемент будет либо дочерним элементом корня, либо дочерним элементом второго по величине.

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