11/7/10

Heap sorting Class

Heap Sorting class
template T&  PQueue::min(){
  return heap[0];
}
template T& PQueue ::extractMin(){
  //cout<<"12"<
  if(!heapsize)throw runtime_error(" the priority queue is empty\n");
  T *min=new T;
  //cout<<"13"<
  min[0]=heap[0];
  //cout<<"14"<
  //cout<<"heapsize:"<<
  swap(heap[0],heap[--heapsize]);//heap[0]=heap[heapsize--];
  //cout<<"15"<
  minHeapify(0);
  //cout<<"16"<
  return min[0];

templatevoid PQueue::minHeapify(int i){
  int l=i*2+1;//important indexing from zero
  int r=(i+1)*2;//important indexing from zero
  int lowest;
  //cout<<"17"<
  if(lheap[l]){lowest=l;}
  else {lowest=i;}
  if(rheap[r]){lowest=r;}
  if(lowest!=i){
    //cout<<"21 lowest="<<
    //cout<<<" heap["<<<"]="<<
    //cout<<<<"before tree is:"<
    //print();
    //cout<
    swap(heap[lowest],heap[i]);
    //cout<<"after swap:"<<<" heap["<<<"]="<<
    //cout<<<<"after tree is:"<
    //print();
    //cout<
    //cout<<"22"<
    minHeapify(lowest);
    //cout<<"23"<
  }
}
template void PQueue::swap(T &p,T &q){
  T tmp=p;//code_h tmp
  p=q;
  q=tmp;
}
template void PQueue::Delete(int e){
  if(!heapsize)throw runtime_error(" the priority queue is empty\n");
  T *min=new T;
  swap(heap[e],heap[--heapsize]);//if indexing from 1 for heapsize then:heap[0]=heap[heapsize--];
  minHeapify(e);
}
templatevoid PQueue::increaseKey(int e){
  heap[e]++;
  minHeapify(e);
}
templatevoid PQueue::decreaseKey(int e){
  heap[e]--;
  minHeapify(e);
}
templatevoid PQueue::insert(T &e){
  //cout<<"43"<
  if(heapsize>=n) throw runtime_error("invalid address :you are inserting more than n(size)\n");
  heap[heapsize]=e;//heapsize begin from 0
  buildheap(heapsize++);
}
templatevoid PQueue::insert(T *e){
  //cout<<"53"<
  if(heapsize>=n) throw runtime_error("invalid address :you are inserting more than n(size)\n");
  heap[heapsize]=*e;//heapsize begin from 0
  //cout<<"60"<
  buildheap(heapsize++);
}
templatevoid PQueue::buildheap(int h){
  while(h>0 && heap[h] s=(k-1)/2
      swap(heap[(h-1)/2],heap[h]);
      h=(h-1)/2;
  }
}
templatebool PQueue::empty() const{
  return heap==heap+heapsize;
}
templatevoid PQueue::print() const{
  int i=0;
  cout<<"the elements in the PriorityQueue:"<
  while(i
    cout<<
    i++;
  }
}

3 comments:

leave me messege