c++ - 使用递归检查 vector 是否为最小堆

Question

我正在尝试编写一个程序来检查 vector 是否为最小堆。我一直在查看来自 here 的代码.我理解他们为什么使用 2*i+2 来与 n 进行比较，因为索引有一个转折点，其中 vector/数组(我的使用 vector )中的值成为叶节点。我不明白的是为什么他们在递归调用函数时一直使用 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

What I don't understand is why they keep using 2*i + 1 and 2*i + 2 as the index when they call the function recursively.

例如，您的堆数据结构如下。这些值存储在一个数组中，比如 A[i], i = 0, 1, …, 7。在这张图片中，蓝色圆圈 i = 3 = 2*1+1 和 i = 4 = 2*1+2 是绿色圆圈 的 child 我 = 1

像这样，一般来说，父i的左 child 有一个索引2*i+1，右 child 有索引 2*i+2. This is very general child-parent relationships in binary heap maps.这就是为什么他们在递归调用函数时一直使用2*i+1和2*i+2作为索引的原因。