Мне нужно создать ФУНКЦИЮ на С++, чтобы ПРОВЕРИТЬ, является ли массив A минимальной кучей или нет? Если это Min Heap, верните true, иначе верните false

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. У листьев нет дочерних элементов.

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


min-heap
person Umair Mahmood    schedule 20.09.2015    source источник
comment
Для этого уже есть функция C++. Не нужно писать свое. std::is_heap.   -  person Raymond Chen    schedule 20.09.2015

Ответы (1)


arrow_upward
0
arrow_downward

Вы можете использовать код ниже, чтобы получить требуемый ответ. вам нужно повторять, пока вы не проверили все узлы в дереве. здесь я делаю это, проверяя, выполняется ли цикл до размера / 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;
    }
}
person Shuaib Ahmed    schedule 22.09.2015
comment
Если мой массив имеет размер = 5, то цикл for будет выполняться 5 раз, то есть от 1 до 5. Когда i = 3, тогда (a[3]‹a[6] && a[3]‹a[7]), но a[6] или a[7] не существует в моем массиве, так как мой массив имеет размер = 5 - person Umair Mahmood; 23.09.2015
comment
У меня нет отладчика, чтобы проверить прямо сейчас, но это должно работать! - person Shuaib Ahmed; 23.09.2015