مشکل در کد برنامه برای heap

[sa1378]

سلام
این کد برای اضافه کردن عدد به یه max heap هست
برای اولین بار وارد کردن درست کار میکنه
ولی وقتی برای دومین بار یه عدد جدید وارد میکنم اشتباه خروجی میده
لطفا اشکال یابی کنید
#include <cstdlib>
#include <iostream>

using namespace std;

int main()
{
int a[100]={0,20,15,2,14,10};
int i=6;
start:

cin>>a[i];

for(;i!=1;)
{
if (a[i]>a[i/2])
{
int extra=a[i];
a[i]=a[i/2];
a[i/2]=extra;
}
i/=2;
}
for(int j=1;j<=100;j++)
{
if(a[j]!=0)
cout<<a[j]<<" ";

if (a[j]==0)
break;
}
cout<<endl;
i++;
goto start;

system("PAUSE");
return EXIT_SUCCESS;
}

[مسعود اقدسی فام]

اون بالا i = 6 هست. داخل حلقه تا i = 1 پایین می‌یاد و می‌ره قبل از پرش i = 2 می‌‌شه. در حالی که اونجا i = 7 باید باشه. اندیس i که نشانگر انتهای آرایه هست رو نباید داخل حلقه برای محاسبه‌ی محل درست عنصر جدید تغییر بدید.

[sa1378]

اون بالا i = 6 هست. داخل حلقه تا i = 1 پایین می‌یاد و می‌ره قبل از پرش i = 2 می‌‌شه. در حالی که اونجا i = 7 باید باشه. اندیس i که نشانگر انتهای آرایه هست رو نباید داخل حلقه برای محاسبه‌ی محل درست عنصر جدید تغییر بدید.

دستت درد نکنه
یه متغیر کمکی تعریف کردم بجای i توی حلقه

[sa1378]

حالا یه کد به این اضافه کردم که بیاد به ترتیب اینارو مرتب کنه
ولی بازم خروجیش اشتباهه
#include <cstdlib>
#include <iostream>

using namespace std;

int main()
{
int a[100]={0,20,15,2,14,10};
int i=6;
start:

cin>>a[i];
int k=i;
for(;k!=1;)
{
if (a[k]>a[k/2])
{
int extra=a[k];
a[k]=a[k/2];
a[k/2]=extra;
}
k/=2;
}
for(int j=1;j<=100;j++)
{
if(a[j]!=0)
cout<<a[j]<<" ";

if (a[j]==0)
break;
}
cout<<endl;

int s;
cin>>s;
if (s==1)
{
i++;
goto start;
}
else if (s==2)
{
for(;a[1]!=0;)
{
int x=1;
a[x]=a[i] ;
a[i]=0;
for(;a[x]<a[x*2] || a[x]<a[x*2+1];)
{
cout<<a[x]<<" ";
if(a[x*2]>a[x*2+1])
{
int extra2=a[x];
a[x]=a[x*2];
a[x*2]=extra2;
}
else if(a[x*2]<=a[x*2+1])
{
int extra2=a[x];
a[x]=a[x*2+1];
a[x*2+1]=extra2;

}
}
}

}
cout<<endl;

system("PAUSE");
return EXIT_SUCCESS;
}





کلا من اشکال یابی کدم ضعیفه
چه پیشنهادی برای این دارین؟
اگه میگین برنامه زیاد ببینم یه سایتی چیزی معرفی کنید

[مسعود اقدسی فام]

چند تا مورد که اشکال اساسی هستن و دیدم:

۱- اگه شرط حلقه‌ی for‌ داخلی درست باشه یعنی درخت حالت درست رو نداره و باید جابجا بشن که خب انجامش می‌دید. اما چرا چاپ می‌کنید قبل از جابجایی؟ چی رو اونجا قصد دارید چاپ کنید وقتی درخت در حالت درستی نیست؟ محل چاپ درست نیست.

۲- وقتی با x محل جابجا شدن رو تشخیص می‌دید، چرا x دیگه تغییر نمی‌کنه؟ باید تا برگ پایین بیاد و مطمئن بشه که دیگه امکان جابجا شدن وجود نداره.

این لینکا رو مطالعه کنید:


http://algorithmha.ir/post-%D9%85%D8%B1%D8%AA%D8%A8-%D8%B3%D8%A7%D8%B2%DB%8C-%D9%87%D8%B1%D9%85%DB%8C.aspx

http://www.algorithmha.ir/post-%D8%AF%D8%B1%D8%AE%D8%AA-%D9%87%DB%8C%D9%BE.aspx

[a.r.khoshghalb]

میدونی که اگر بخوای از heap استفاده کنی لازم نیست پیاده سازیش کنی! صف اولویت دار (Priority queue) دقیقا معادل heap هست (در واقع خود heap هست).
مگر اینکه نیتت از پیاده سازی تمرین بوده باشه...

[sa1378]

میدونی که اگر بخوای از heap استفاده کنی لازم نیست پیاده سازیش کنی! صف اولویت دار (Priority queue) دقیقا معادل heap هست (در واقع خود heap هست).
مگر اینکه نیتت از پیاده سازی تمرین بوده باشه...

برای تمرین هست
ولی اون روشی که میگید چی هست؟

[a.r.khoshghalb]

روش نیست!
صف اولویت دار (priority queue) یه داده ساختاره (Data Structure) که توی خود ++C نوشته شده و آماده هست.

#include <queue>

int main()
{
priority_queue<int> p;
}


که می توانید از توابع زیر استفاده کنید:

p.front();
p.pop();
p.push(A number);


الان یه مین هیپ درست شده که p.front()، روت (Root) آن را بر می گرداند.
p.pop روت آن را پاک کرده و دوباره درخت را heapify می کند.
p.push هم که یک عدد به آن اضافه می کند.

اگر کامل متوجه نشدید اول پیشنهاد می کنم که IDE خودتون رو باز کنید و یکم بازی کنید باهاش... اگه باز هم متوجه نشدید تو اینترنت سرچ کنید مطالب خوبی به دست میاد احتمالا!

[sa1378]

روش نیست!
صف اولویت دار (priority queue) یه داده ساختاره (Data Structure) که توی خود ++C نوشته شده و آماده هست.

#include <queue>

int main()
{
priority_queue<int> p;
}


که می توانید از توابع زیر استفاده کنید:

p.front();
p.pop();
p.push(A number);


الان یه مین هیپ درست شده که p.front()، روت (Root) آن را بر می گرداند.
p.pop روت آن را پاک کرده و دوباره درخت را heapify می کند.
p.push هم که یک عدد به آن اضافه می کند.

اگر کامل متوجه نشدید اول پیشنهاد می کنم که IDE خودتون رو باز کنید و یکم بازی کنید باهاش... اگه باز هم متوجه نشدید تو اینترنت سرچ کنید مطالب خوبی به دست میاد احتمالا!

گرفتم چی شد
فقط یه چیزی
مقدار دهی اولیه چی میشه؟

[a.r.khoshghalb]

مقدار دهی اولیه چی؟ queue؟
اگر درست فهمیده باشم سوالتو مقدار اولیه نمی خواد باشه تو queue!
عین اینه که heap اولش هیچ عددی توش نیست...
اگر جوابتو نگرفتی و من اشتباه فهمیدم منظورتو دوباره دقیق تر بپرس :لبخندساده: