Max Heap

[eas_m66]

سلام
من برنامه maxheap رو نوشتم ولی مشکل داره.کدش رو میزارم اگه کسی تونست کمک کنه ممنون می شم.
کد:


#include<iostream.h>
#include<conio.h>
void swap(int x,int y){
int t;
t=x;
x=y;
y=t;
}
class Heap
{
public:
Heap(); //constructor
void Make_Heap();
void Make_MaxHeap();
void Max_Heapfy(int);
void Insert(int);
void Remove(int);
void Print();
private:
int table[100];
int Heap_size;
};
Heap::Heap()
{
cout<<"Please Enter The Number of nodes:";
cin>>Heap_size;
cout<<"please enter The value of node:";
for(int i=1;i<=Heap_size;i++)

cin>>table[i];
Make_MaxHeap();
}
//********************************
void Heap::Make_MaxHeap()
{
for(int i=Heap_size/2;i>0;i--)
Max_Heapfy(i);
}
//*********************************
void Heap::Max_Heapfy(int i)
{
int L=2*i;
int R=2*i+1;
int largest=i;
if(R<=Heap_size&&table[i]<table[R])
largest=R;
if(L<=Heap_size&&table[largest]<table[L])
largest=L;
if(largest!=i)
{
swap(table[i],table[largest]);
Max_Heapfy(largest);
}
}
//**********************************
void Heap::Insert(int num)
{
Heap_size++;
table[Heap_size]=num;
for(int i=Heap_size/2;i>0;i--)
Max_Heapfy(i);
}
//**********************************
void Heap::Remove(int num)
{
int i,index;
if(Heap_size>0)
{
for(i=1;i<=Heap_size;i++)
if(table[i]==num)
{
index=i;
break;
}
if(index!=Heap_size)
{
swap(table[index],table[Heap_size]);
Heap_size--;
for(i=Heap_size/2;i>0;i--)
Max_Heapfy(i);
}
}
}
//*********************************
void Heap::Print()
{
for(int i=1;i<=Heap_size;i++)
cout<<table[i]<<' ';
}
//*********************************
int main()
{
Heap H;
int n,i;
H.Make_MaxHeap();
H.Print();
cout<<"\n Enter A New Number:";
cin>>n;
H.Insert(n);
H.Print();
cout<<"Enter A number to remove it frome Heap:";
cin>>n;
H.Remove(n);
H.Print();
}

[pesar irooni]

با عرض سلا م وخسته نباشی خدمت شما دوست عزیز.
ببینید من برنامه شما رو دیدم ولی انگار شما مقصودتون رو از نوشتن یک maxHeap نمی دونید. maxHeap درختیه که از اون تو مرتب سازی از نوع HeapSort استفاده می کنند. بنابر این هنگام حذف یک عنصر تنها باید از ریشه حذف کرد و سپس دوباره درخت رو مرتب کرد (نه اینکه هر عنصر رو از هر کجا دلمون خواست حذف کنیم). من استراتژی شما رو تو متد max_heapfy دقیق متوجه نشدم ولی برای درج یک عنصر توی maxHeap ابتدا باید اون رو به آخرین عنصر آرایه اضافه کرد (برای اینکه ساختار درخت به صورت دودویی کامل بماند) و سپس درخت رو مرتب کرد. یعنی عنصر جدید به سمت جایگاه اصلی اش تو دخت به بالا حرکت می کنه و در صورت لزوم جاش رو با پدرش عوض می کنه . من این کار رو تو تابع عمل درج تو این درخت انجام دادم و برات نوشتم؛ امیدوارم بدردت بخوره.


void maxHeapInsert(int nodes[], int n, int x)
{
int i = n+1; // n+1 is location in end of tree
int j = i/2; // i div 2 ** j is index of i's parrent
while((j>0) && (nodes[j]<x((
// j>0 that is dosent arrive to root
// nodes[j]<x that is x is larger than its parent
}
nodes[i] = nodes[j]; //replace parent in child
i = j;
j = i/2; // j is parent of i
{

nodes[i] = x; // i is right location of x
{


اگه خواستی الگوریتم حذفش هم برات می نویسم.

[404_3140]

بنابر این هنگام حذف یک عنصر تنها باید از ریشه حذف کرد و سپس دوباره درخت رو مرتب کرد (نه اینکه هر عنصر رو از هر کجا دلمون خواست حذف کنیم).
چرا که نه؟ می تونیم از هر جای درخت حذف کنیم. فقط کافیه جای اون عضوی رو که قراره حذف بشه با عضو آخری heap عوض کنیم،‌سایر heap رو ۱ واحد کم کنیم، و بعد اون عنصر رو bubble-up یا bubble-down کنیم با توجه به این که max heap یا min heap داریم.

[pesar irooni]

چرا که نه؟ می تونیم از هر جای درخت حذف کنیم.
سلام آقای عدد. ممنون از راهنماییتون.
ولی ممکنه بفرمایید فایده این کار چیه و کجا کاربرد داره؟

با تشکر

[404_3140]

در جاهای بسیاری!!تعریف ش رو گفتم مثال که براش خیلییی زیاد هست

[donya1234]

سلام میشه الگوریتم و کد حذفش رو هم بزارید؟