как построить кучу деревьев?

Question

Я понимаю алгоритм построения дерева кучи (макс или мин), но я не понимаю его код:

Первый: Как этот цикл создает максимальную кучу?почему мы начали i с n / 2-1?

// Build heap (rearrange array) 
for (int i = n / 2 - 1; i >= 0; i--) 
    heapify(arr, n, i); 

, и это функция Heapify:

Во-вторых: как мы предположили, что наибольшее значение«i»?

В-третьих: почему мы снова накапливаемся в последней строке?

// To heapify a subtree rooted with node i which is 
// an index in arr[]. n is size of heap 
void heapify(int arr[], int n, int i) 
{ 
    int largest = i; // Initialize largest as root 
    int l = 2*i + 1; // left = 2*i + 1 
    int r = 2*i + 2; // right = 2*i + 2 

    // If left child is larger than root 
    if (l < n && arr[l] > arr[largest]) 
        largest = l; 

    // If right child is larger than largest so far 
    if (r < n && arr[r] > arr[largest]) 
        largest = r; 

    // If largest is not root 
    if (largest != i) 
    { 
        swap(arr[i], arr[largest]); 

        // Recursively heapify the affected sub-tree 
        heapify(arr, n, largest); 
    } 
} 

Код и алгоритм, который я получил, взяты из GeeksForGeeks

Answer 1

Давайте сделаем это с очень простым примером построения максимальной кучи, который, я думаю, ответит на ваши вопросы.Представьте, что у вас есть массив [3, 1, 6, 4, 7, 9].Это соответствует этому двоичному дереву:

     3
  1     6
4   7 9

Идея алгоритма состоит в том, чтобы сдвинуть вещи в кучу на свое место.Ваш первый вопрос: почему мы начинаем с i = n//2.Простой ответ заключается в том, что любой узел в положении, превышающем i // 2, является листом;у него нет детей, и поэтому его нельзя оттолкнуть.На самом деле, мы можем начать с (n-1)//2, потому что если n является четным, то существует первый неконечный узел, а для нечетного числа (n-1)//2 == n/2.

Так что в этом случае i=2.Ваш следующий вопрос: почему мы предполагаем, что элемент с индексом i является самым большим.Мы неМы начнем с этого, потому что мы должны найти самый большой из трех предметов (предмет в i и его двух дочерних элементах).Таким образом, мы просто по умолчанию i.Вы можете, если хотите, установить largest для левого потомка, а затем выполнить сравнения.Но нет особой причины делать это таким образом.Вы должны начать с что-то , и элемент с индексом i является самым простым.

В этом случае элемент с индексом i равен 6. Мы проверяем потомков элементаи обнаружим, что 9 больше, поэтому мы меняемся местами.Результат:

     3
  1     9
4   7 6

Мы уменьшаем i, давая нам i=1.Глядя на предмет там и его дочерние элементы, мы видим, что число 7 является самым большим, поэтому мы поменяли местами два элемента, получив:

     3
  7     9
4   1 6

И теперь мы в корне.9 является наибольшим среди корня и его потомков, поэтому мы поменяемся местами:

     9
  7     3
4   1 6

И вот ответ на ваш третий вопрос: почему рекурсивный вызов heapify?Вы должны толкнуть предмет до кучи, насколько это возможно.Здесь 3 меньше 6, поэтому мы должны поменять местами эти элементы:

     9
  7     6
4   1 3

Answer 2

Наибольший дочерний индекс ci родительского узла:

ci = 2*i + 2 < size
i < (size - 2)/2
i < size/2 - 1

, но вам нужно включить size/2 - 1, поскольку у узла может быть только один дочерний элемент, а i проходит весь путьв ноль, так как все эти узлы являются родительскими узлами.Что касается рекурсии, вам нужно применить правило max-heap после перестановки.

Answer 3

1) Рассмотрим структуру кучи

              M
       K            L
   G       H     I     J  
 A  B    C  D   E  F  

Последний уровень содержит не более половины всех элементов ((n+1)//2), поэтому элемент с индексом n/2-1 всегда является родителем последних элементов на последнем уровне,И начиная с этого индекса и пройдя налево, мы упорядочиваем мини-кучи из трех элементов, затем переходим вверх и влево, мы упорядочиваем кучу из семи элементов и т. Д.

2) Это простая инициализация условной задачи- если мы найдем более крупного потомка, он заменит родителя

3) Если родителя заменили, он переместился вниз и может быть меньше, чем у новых потомков, поэтому мы должны проверить (малый элемент падает)