Downheap реализация в C

Question

У меня есть исходный код Downheap на языке C, который будет перемещать элементы вниз, не нарушая свойства кучи (значение каждого узла больше / меньше или равно значению его родителя, с элемент минимального / максимального значения в root.) в любых узлах дерева.

downheap(int k)
{
    int temp, i;
    temp = a[k];
    while(k <= N/2)
    {
        i = 2*k;
        if(i < N && a[i] < a[i+1]) i++;
        if(temp > a[i]) break;
        a[k] = a[i]; k = i;
    }
    a[k] = temp;
}

N - общее количество узлов массива a. Я спросил, может ли эта программа перемещаться вниз по узлам слева направо, чтобы сохранить свойство полного двоичного дерева ? Как это доказать, потому что нет свойства, что правый узел должен быть меньше / больше левого.

Answer 1

downheap(int k) // k is the index of the item in the heap 
{
  int temp, i;
  temp = a[k]; // Use temp to store the item
  while (k <= N / 2) // Make sure that we don't get outside of the heap boundaries
  {
    i = 2 * k; // Helper line to be used as an index for the children of the node
    if (i < N && a[i] < a[i + 1]) i++; // check which of the children is 
    // Bigger to exchange with the item
    if (temp > a[i]) break; // Item already in-place
    a[k] = a[i];
    k = i; // Exchange item with the children we found to be the biggest
  }
  a[k] = temp; // Put the item in its correct position
}

Надеюсь, что рекомендация полезна