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

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

0 голосов
/ 14 октября 2018

Я пытаюсь написать программу, которая проверяет, является ли вектор минимальной кучей.Я искал код от здесь .Я понимаю, почему они используют 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;
  }

1 Ответ

0 голосов
/ 14 октября 2018

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

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

picture

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

...