使用递归检查向量是否为最小堆

Question

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

我的测试代码（returns 0，什么时候应该return 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是绿色圆圈i = 1

的children

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

使用递归检查向量是否为最小堆

Checking if a vector is a min heap using recursion

c++

vector

min-heap

data-structures