Сколько сравнений нужно для 8-элементной двоичной кучи?

Построение кучи снизу вверх происходит линейно, сверху вниз (или постепенно) — O(n log n).

Старайтесь следовать реальному алгоритму, а не просто рисовать деревья. Я видел, как на слишком многих экзаменах люди рисовали красивые деревья, но не следовали алгоритму, что обычно приводило к неправильным результатам, неэффективности и т. д. Дерево — это просто «идея», а не «метод». Метод здесь фактически использует массив.

Изменить: снизу вверх начинается с половины размера кучи. Итак, при сравнении элементов 4 и 7:

Level 3: 4 < 8
Level 2: 3 < 7, 3 < 6
         2 < 5, 2 < 4
Level 1: 1 < 3, 1 < 2

Edit2: Максимальная куча:

Level 3: 4 < 8 -> Swap 4-8.
Level 2: 3 < 7, 3 < 6 -> Swap 3-7, fix heap down (no-op)
         2 < 5, 2 < 8 -> Swap 2-8, fix heap down:
           2 < 4 -> Swap 2-4, fix heap down (no-op)
Level 1: 1 < 7, 1 < 8 -> Swap 1-8, fix heap down
           1 < 4, 1 < 5 -> Swap 1-5, fix heap down (no-op)
Resulting heap:
          8
      5       7
    4   1   6   3
   2

Делает 10 сравнений. Поэтому я считаю, что либо в вашем вопросе с домашним заданием была ошибка, либо вы неправильно ответили на вопрос. То, что построение кучи снизу вверх занимает O(n), не означает, что требуется ровно n сравнений. Для точных границ, проверьте учебник.

Я считаю, что принятый ответ неверен.

На самом деле построение кучи снизу вверх — это O(n), но это только верхняя граница, применимая к общему случаю. В конкретных случаях можно работать лучше, например, когда у нас есть 8 элементов. Ниже я представлю хотя бы один способ, которым можно построить кучу из 8 элементов за 8 сравнений.

Допустим, у нас есть 8 элементов {A, B, C, D, E, F, G, H}, и мы ничего не знаем об их относительном порядке. Начнем с сравнения любых четырех пар восьми элементов. После этого шага мы выполнили 4 сравнения и теперь имеем 4 «упорядоченные» пары, как показано ниже:

A > B, C > D, E > F, G > H

Теперь обратите внимание, что с помощью 1 сравнения мы можем соединить две пары в дереве N = 4. Например, если мы возьмем первые две пары и сравним A и C, мы получим либо дерево слева внизу (если A > C) или тот, что справа (если C > A):

    A     |       C 
  C   B   |     A   D
D         |   B

Мы применяем тот же процесс к двум другим парам, в итоге получив два дерева N = 4, используя пока 6 сравнений. У нас есть что-то вроде:

    A              E 
  C   B   and    G   F
D              H

С помощью одного дополнительного сравнения мы можем решить, какой из них имеет более высокий порядок между A или E. Скажем, A > E без ограничения общности. На данный момент мы использовали 7 сравнений. Наконец, мы используем наше последнее оставшееся сравнение, чтобы определить порядок между элементами ниже A (B и C), и используем эту информацию, чтобы изменить дерево слева вверху на один из двух ниже (B > C слева, C > Б справа):

 A        |   A     
   B      |     C   
 C   D    |   B   D

Наконец, поскольку мы уже знаем, что A > E, теперь легко соединить два дерева, которые у нас есть (одно с корнем в E и одно с корнем в A), как показано ниже:

         A
    E         B
  G   F     D   C
H

И мы закончили, у нас есть куча из 8 элементов, построенных с 8 сравнениями. Надеюсь все понятно хахаха