Я должен создать FUNCTION в C++, чтобы проверить, является ли массив A Min Minap или нет? Если это 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] с использованием формулы Tree[K/2], а его левый дочерний элемент равен Tree[2K], а его правый child это Tree[2K+1], и это верно только в том случае, если мы начинаем наш массив с 1, а не с 0.

Есть три случая, чтобы проверить, является ли мой массив минимальной кучей или нет:
1. Внутренние узлы имеют как левого, так и правого потомка.
2. Последний узел может иметь только одного дочернего, который остается дочерним.
3. У листьев нет ни одного ребенка.

но я не могу понять, как я могу сделать это в виде кода в моей программе... PLZ изменить мою программу или дать мне подсказку, как я могу это сделать....????

Answer 1

Вы можете код ниже, чтобы получить требуемый ответ. вам нужно повторять, пока вы не проверили все узлы в дереве. здесь я делаю это, проверяя, работает ли цикл до размера /2 или нет. Предположим, если массив имеет размер, я бы проверил его на размер /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;
    }
}