C++ Max Heap class

Ocak 26, 2008 tarihinde C/C++ kategorisi altında kayda geçti

Here is the max heap class code which is implemented by a vector. vector holds the hnode class object pointers. this code is a little fantasy. because of this you can implement more efficient heap classes looking at this code. this code is just for giving hints. hadi rast gele agalar :)

hnode class

class hnode{
 
public:
string file;
int size;
hnode(string s,int a);
};
 
hnode::hnode(string s,int a){
 
file=s;
size=a;
 
}

max heap class

class heap{
 
private:
 
vector files;
 
public:
void insert(string file,int size);
void remove(string file);
void change(string file,int delta);
void swap(hnode *a,hnode *b);
void largest();
void display();
 
};
 
void heap::display(){
 
int cnt=0;
while(cnt
cout << cnt << " " << files.at(cnt)->file << " " << files.at(cnt)->size << endl;
cnt++;
}
}
 
void heap::largest(){
 
cout << files.at(0)->file <<"  " << files.at(0)->size << endl;
}
 
void heap::insert(string file,int size){
 
hnode *temp=new hnode(file,size);
files.push_back(temp);
 
size=files.size()-1;
 
while(files.at(size)->size > files.at((size-1)/2)->size){
swap(files.at(size),files.at((size-1)/2));
size=(size-1)/2;
}
}
 
void heap::swap(hnode *a,hnode *b){
 
int temp;
string demp;
 
temp=a->size;
a->size=b->size;
b->size=temp;
 
demp=a->file;
a->file = b->file;
b->file= demp;
}
 
void heap::remove(string file){
 
int cnt=0;
 
while(files.at(cnt)->file!=file)
cnt++;
 
swap(files.at(cnt),files.at(files.size()-1));
 
files.pop_back();
 
if(files.at( (cnt-1)/2 )->size < files.at(cnt)->size ){
 
while(files.at(cnt)->size > files.at((cnt-1)/2)->size){
swap(files.at(cnt),files.at((cnt-1)/2));
cnt=(cnt-1)/2;
}
}else{
while(true){
 
hnode *cur=files.at(cnt);
 
if((2*cnt)+1> files.size()-1)
return;
if((2*cnt)+1 <= files.size()-1 && (2*cnt)+2 > files.size()-1){
hnode *left=files.at((2*cnt)+1);
if(left->size > cur->size)
swap(cur,left);
return;
}
 
if((2*cnt)+1 < files.size() && (2*cnt)+2 < files.size()){
 
hnode *left=files.at((2*cnt)+1);
hnode *right=files.at((2*cnt)+2);
 
if(cur->size > left->size && cur->size > right->size){
return;
}else if( cur->size > left->size && cur->size < right->size ){
swap(cur,right);
cnt=(2*cnt)+2;
}else if(cur->size < left->size && cur->size > right->size ){
swap(cur,left);
cnt=(2*cnt)+1;
}else{
if(left->size > right->size){
swap(cur,left);
cnt=(2*cnt)+1;
}else{
swap(cur,right);
cnt=(2*cnt)+2;
}
}
}
}
 
}
}
 
void heap::change(string file,int delta){
 
int	cnt=0;
 
while(files.at(cnt)->file!=file)
cnt++;
files.at(cnt)->size=files.at(cnt)->size + delta;
 
}