Каково максимальное количество сравнений для кучи массива?

Question

Существует ли общая формула для расчета максимального количества сравнений для кучи данных n элементов?

Если нет, то является ли 13 максимальным числом сравнений для кучи массива из 8 элементов?

Мои рассуждения таковы:

at h = 0, 1 node, 0 comparisons, 1* 0 = 0 comparisons 

at h = 1, 2 nodes, 1 comparison each, 2*1 = 2 comparisons

at h = 2, 4 nodes, 2 comparisons each, 4*2 = 8 comparisons

at h = 3, 1 node, 3 comparisons each, 1*3 = 3 comparisons

Total = 0 + 2 + 8 + 3 =13

Answer 1

Принятая теория состоит в том, что куча сборки требует не более (2N - 2) сравнений. Таким образом, максимальное количество требуемых сравнений должно быть 14. Мы можем достаточно легко это подтвердить, изучив кучу из 8 элементов:

             7
           /   \
          3     1
         / \   / \
        5   4 8   2
       /
      6

Здесь 4 конечных узла никогда не сместятся вниз. Узлы 5 и 1 могут двигаться вниз на 1 уровень. 3 может двигаться вниз на два уровня. И 7 может двигаться вниз на 3 уровня. Таким образом, максимальное количество ходов уровня:

(0*4)+(1*2)+(2*1)+(3*1) = 7

Каждый ход уровня требует 2 сравнений, поэтому максимальное количество сравнений будет 14.