Java Reference
In-Depth Information
/
**
Max-heapimplementation
*
/
publicclassMaxHeap<EextendsComparable<?superE>>{
privateE[]Heap; //Pointertotheheaparray
privateintsize; //Maximumsizeoftheheap
privateintn; //Numberofthingsinheap
/
**
Constructorsupportingpreloadingofheapcontents
*
/
publicMaxHeap(E[]h,intnum,intmax)
{Heap=h;n=num;size=max;buildheap();}
/
**
@returnCurrentsizeoftheheap
*
/
publicintheapsize(){returnn;}
/
**
@returnTrueifposaleafposition,falseotherwise
*
/
publicbooleanisLeaf(intpos)
{return(pos>=n/2)&&(pos<n);}
/
**
@returnPositionforleftchildofpos
*
/
publicintleftchild(intpos){
assertpos<n/2:"Positionhasnoleftchild";
return2
*
pos+1;
}
/
**
@returnPositionforrightchildofpos
*
/
publicintrightchild(intpos){
assertpos<(n-1)/2:"Positionhasnorightchild";
return2
*
pos+2;
}
/
**
@returnPositionforparent
*
/
publicintparent(intpos){
assertpos>0:"Positionhasnoparent";
return(pos-1)/2;
}
/
**
Insertvalintoheap
*
/
publicvoidinsert(Eval){
assertn<size:"Heapisfull";
intcurr=n++;
Heap[curr]=val; //Startatendofheap
//Nowsiftupuntilcurr'sparent'skey>curr'skey
while((curr!=0)&&
(Heap[curr].compareTo(Heap[parent(curr)])>0)){
DSutil.swap(Heap,curr,parent(curr));
curr=parent(curr);
}
}
Figure5.19
An implementation for the heap.
