Проверка, является ли вектор минимальной кучей, используя рекурсию

Question

Я пытаюсь написать программу, которая проверяет, является ли вектор минимальной кучей. Я искал код здесь. Я понимаю, почему они используют 2*i+2 для сравнения с n, поскольку есть переломный момент с индексом, когда значения в векторе / массиве (мой использует вектор) становятся листовыми узлами. Я не понимаю, почему они продолжают использовать 2*i + 1 и 2*i+2 в качестве индекса, когда они вызывают функцию рекурсивно. Разве они не должны использовать i + 1 для доступа к левому узлу и i + 2 для доступа к правому? Но я попробовал это, и я получил ошибку сегментации.

    bool checkMinHeap(int A[], int i, int n)
    { 
       // if i is a leaf node, return true as every leaf node is a heap
       if (2*i + 2 > n)
       return true;

       // if i is an internal node        

      // recursively check if left child is heap
      bool left = (A[i] <= A[2*i + 1]) && checkMinHeap(A, 2*i + 1, n);

      // recursively check if right child is heap (to avoid array out
     // of bound, we first check if right child exists or not)
     bool right = (2*i + 2 == n) || 
            (A[i] <= A[2*i + 2] && checkMinHeap(A, 2*i + 2, n));

     // return true if both left and right child are heap
     return left && right;
  }

Их тестовый код:

    int main()
    {
       int A[] = {1, 2, 3, 4, 5, 6};
       int n = sizeof(A) / sizeof(int);

       // start with index 0 (root of the heap)
       int index = 0;

       if (checkMinHeap(A, index, n))
           cout << "Given array is a min heap";
       else
           cout << "Given array is not a min heap";

       return 0;
  }

Мой тестовый код (возвращает 0, когда должен возвращать 1):

   int main (void)
   {
      vector <int> test;
      test.push_back(1);
      test.push_back(2);
      test.push_back(3);
      test.push_back(4);
      test.push_back(5);
      test.push_back(9);
      test.push_back(3);
      test.push_back(19);
      cout << isMinHeap(test,0) << endl;
  }

Answer 1

Я не понимаю, почему они продолжают использовать 2*i + 1 и 2*i + 2 в качестве индекса, когда они вызывают функцию рекурсивно.

Например, ваша структура данных кучи следующая. Эти значения хранятся в массиве, скажем A[i], i = 0, 1, …, 7, На этой картинке синие круги i = 3 = 2*1+1 а также i = 4 = 2*1+2 дети зеленого круга i = 1

Вот так, в общем, левый потомок родителя i имеет индекс 2*i+1 и правый имеет индекс 2*i+2 , Это очень общие дочерние и родительские отношения в двоичных картах кучи. Это причина, почему они продолжают использовать 2*i+1 а также 2*i+2 в качестве индекса, когда они вызывают функцию рекурсивно.