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

Question

Это вопрос с домашней работой, и меня просят показать, что Binary Heap из 8 элементов требует 8 сравнений.

, но когда я использую пример, такой: 1 2 3 4 5 6 7 8 Яне уверен, должен ли я пойти снизу вверх или сверху вниз.но в любом случае, я попробовал их обоих.

Сверху вниз: я сделал это за 8 шагов, но когда я посчитал количество сравнений, я получил 13: S

В итоге: Я сделал это в 7 шагов, но когда я посчитал количество сравнений, я получил 10: S

После попытки алгоритма вот сравнение, которое я получил:

1. H [L] = 8> H [i] = 4
2. H [L] = 8> H [i] = 2, H [r] = 5> H [наибольший] = 8
3. H [L] = 4> H [i] = 2
4. H [L] = 6> H [i] = 3, H [r] = 7> H [Largest] = 6
5. H [L] = 8> H [i] = 1, H [r] = 7
6. H [L] = 4> H [i] = 1, H[r] = 5> H [Largest] = 4

ммм, любая помощь в том, как мне посчитать количество сравнений, чтобы я мог показать их 8?и какой метод я должен использовать (снизу вверх или сверху вниз)?

Answer 1

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

Построение кучи снизу вверх - это фактически 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>B справа):

 A        |   A     
   B      |     C   
 C   D    |   B   D

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

         A
    E         B
  G   F     D   C
H

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

Answer 2

Построение кучи снизу вверх является линейным, сверху вниз (или в приращении) - 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: Max heap:

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 сравнений.Точные оценки можно найти в учебнике.