Реализация Max-heap

Question

Следующий код для реализации max-heap

#include<iostream>
#include<math.h>
using namespace std;
#define  maxn 1000
int x[maxn];

int parent(int i){
    return int(i/2);

}
int left(int i){
    return 2*i;

}
int right(int i){
    return 2*i+1;

}
void  max_heap(int x[],int i,int size){
    int largest;
    int l=left(i);
    int r=right(i);

    if (l<=size &&  x[l]>x[i]){
        largest=l;
    }
    else
    {
        largest=i;
    }
    if (r<=size && x[r]>x[largest]){
    largest=r;
    }
    if (largest!=i)  { int s=x[i];x[i]=x[largest];x[largest]=s;}
    max_heap(x,largest,size);
}




int main(){

 x[1]=16;
 x[2]=4;
 x[3]=10;
 x[4]=14;
 x[5]=7;
 x[6]=9;
 x[7]=3;
 x[8]=2;
 x[9]=8;
 x[10]=1;
  int size=10;
  max_heap(x,2,size);
   for (int i=1;i<=10;i++)
       cout<<x[i]<<"  ";






    return 0;
}

Когда я его запускаю, выдается такое предупреждение:

1>c:\users\datuashvili\documents\visual studio 2010\projects\heap_property\heap_property\heap_property.cpp(36): warning C4717: 'max_heap' : recursive on all control paths, function will cause runtime stack overflow

Скажите, пожалуйста, что не так?

Answer 1

Сообщение говорит вам, что именно не так.Вы не реализовали никаких проверок, чтобы остановить рекурсию.Один умный компилятор.

Answer 2

max_heap функция не имеет базового регистра, то есть оператора возврата.Вы просто рекурсивно вызываете функцию, но никогда не говорите, когда прервать очередной последовательный вызов max_heap.

Кроме того, в вашем примере вы просто вызываете функцию, не удовлетворяющую любому условию.Обычно рекурсия выполняется или не выполняется, когда дело удовлетворено.

Answer 3

Поместите

max_heap(x,largest,size);

внутри последней проверки, например:

if (largest!=i)  
{ 
    int s=x[i];
    x[i]=x[largest];
    x[largest]=s;
    max_heap(x,largest,size);
}

и все готово!

Есть много других проблем с вашим кодом,но чтобы ответить на ваш конкретный вопрос, вышеприведенные изменения подойдут!

Answer 4

скажите, пожалуйста, что не так?

Другая проблема, которую я вижу, состоит в том, что размер вашего массива x равен 10. Но индексы, которые вы используете для установки значений, составляют 1-10.