Heap Sorting class
template T& PQueue::min(){
return heap[0];
}
templateT& 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++;
}
}
;> [i]> ){> ;> ,n> ,n> [(h-1)> ,n> ;> ;> ,n> ;> ,n> ,n> ,n> ,n> ,n> ;> ;> ;> ;> ;> [i]> [lowest]> ;> ;> ;> [i]> [lowest]> ;> ;> ,n> ;> ;> ;> ;> ;> ;> ,n> ,n>
template
return heap[0];
}
template
//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];
}
template
int l=i*2+1;//important indexing from zero
int r=(i+1)*2;//important indexing from zero
int lowest;
//cout<<"17"<
if(l
else {lowest=i;}
if(r
if(lowest!=i){
//cout<<"21 lowest="<
//cout<
//cout<
//print();
//cout<
swap(heap[lowest],heap[i]);
//cout<<"after swap:"<
//cout<
//print();
//cout<
//cout<<"22"<
minHeapify(lowest);
//cout<<"23"<
}
}
template
T tmp=p;//code_h tmp
p=q;
q=tmp;
}
template
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);
}
template
heap[e]++;
minHeapify(e);
}
template
heap[e]--;
minHeapify(e);
}
template
//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++);
}
template
//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++);
}
template
while(h>0 && heap[h]
swap(heap[(h-1)/2],heap[h]);
h=(h-1)/2;
}
}
template
return heap==heap+heapsize;
}
template
int i=0;
cout<<"the elements in the PriorityQueue:"<
while(i
cout<
i++;
}
}