Java Reference
In-Depth Information
/
**
HeapifycontentsofHeap
*
/
publicvoidbuildheap()
{for(inti=n/2-1;i>=0;i--)siftdown(i);}
/
**
Putelementinitscorrectplace
*
/
privatevoidsiftdown(intpos){
assert(pos>=0)&&(pos<n):"Illegalheapposition";
while(!isLeaf(pos)){
intj=leftchild(pos);
if((j<(n-1))&&(Heap[j].compareTo(Heap[j+1])<0))
j++;//jisnowindexofchildwithgreatervalue
if(Heap[pos].compareTo(Heap[j])>=0)return;
DSutil.swap(Heap,pos,j);
pos=j;//Movedown
}
}
/
**
Removeandreturnmaximumvalue
*
/
publicEremovemax(){
assertn>0:"Removingfromemptyheap";
DSutil.swap(Heap,0,--n);//Swapmaximumwithlastvalue
if(n!=0) //Notonlastelement
siftdown(0); //Putnewheaprootvalincorrectplace
returnHeap[n];
}
/
**
Removeandreturnelementatspecifiedposition
*
/
publicEremove(intpos){
assert(pos>=0)&&(pos<n):"Illegalheapposition";
if(pos==(n-1))n--;//Lastelement,noworktobedone
else
{
DSutil.swap(Heap,pos,--n);//Swapwithlastvalue
//Ifwejustswappedinabigvalue,pushitup
while((pos>0)&&
(Heap[pos].compareTo(Heap[parent(pos)])>0)){
DSutil.swap(Heap,pos,parent(pos));
pos=parent(pos);
}
if(n!=0)siftdown(pos);//Ifitislittle,pushdown
}
returnHeap[n];
}
}
Figure5.19
(continued)
