min-heap - 我必须在 C++ 中创建一个函数来检查数组 A 是否是最小堆？如果是 Min Heap 则返回 true 否则返回 false

Question

bool isMinHeap(int A[],int size)
{
    for(int i=1; i<=size; i++)
    {
        if((A[i]<=A[2i]) && (A[i]<=A[2i+1]))
            t=1;
        else
        {
            t=0;
            break;
        }
    }
    if(t==1)
        return true;
    else return false;
}

我在堆栈溢出中搜索这个问题。但是我很难理解编码，因为有人使用了递归过程。

我知道在 Min Heap 中每个父节点都小于或等于其子节点...我也知道我们使用公式 Tree[K/2] 表示 Tree[K] 中的父节点，其左子节点是 Tree[2K]，其右子节点child 是 Tree[2K+1]，只有当我们的数组从 1 而不是 0 开始时才成立。

有三种情况可以检查我的数组是否是最小堆：
1. 内部节点有左右子节点。
2. 最后一个节点可能只有一个左孩子。
3.叶子没有孩子。

但我不明白如何在我的程序中以代码的形式做到这一点......请修改我的程序或给我提示，我该怎么做......？？？？

Answer 1

您可以使用下面的代码来获得所需的答案。您需要进行迭代，直到您检查了树中的所有节点。在这里，我通过检查循环是否运行到 size/2 来做到这一点。假设如果数组的大小我会检查它的 size/2= 5/2 =2 即 (c==2) 我希望它会有所帮助！

     void minheap()        
     {
    int c=0;

for(int i=1;i<=size;i++)
    {
        if(a[i]<a[i*2] && a[i]<a[i*2+1])
        {
              c++;
        }
    }
    if(c==size/2)
    {
        cout<<"Min heap";
        //return true;
    }
    else
    {
        cout<<"Not Min heap";
        //return false;
    }
}