-
public class MaxPQ <Key extends Comparable<Key>> {
-
private Key[] pq;
-
private int N=0;
-
public MaxPQ(int maxN){
-
pq=(Key[])new Comparable[maxN+1];
-
}
-
-
public boolean isEmpty(){
-
return N==0;
-
}
-
-
public int size(){
-
return N;
-
}
-
-
public void insert(Key v){
-
pq[++N]=v;
-
swim(N);
-
}
-
-
private void swim(int k) {
-
while(k>1 && less(k/2,k)){
-
exch(k/2,k);
-
k=k/2;
-
}
-
}
-
-
private boolean less(int i, int j) {
-
return pq[i].compareTo(pq[j])<0;
-
}
-
-
public Key delMax(){
-
Key max=pq[1] ;
-
exch(1,N--);
-
pq[N+1]=null;
-
sink(1);
-
return max;
-
}
-
-
private void sink(int k) {
-
while(2*k<=N){
-
int j=2*k;
-
if(j<N && less(j,j+1))
-
j++;
-
if(!less(k,j))
-
break;
-
exch(k,j);
-
k=j;
-
}
-
}
-
-
private void exch(int i, int j) {
-
Key t=pq[i];
-
pq[i]=pq[j];
-
pq[j]=t;
-
}
-
-
public static void main(String[] args){
-
Integer[] data={100,20,21,28,22,26,80,33,3,2,9,8,7,10,77,66,99,96,91,94};
-
-
MaxPQ<Integer> pq=new MaxPQ<>(data.length);
-
for(int i=0;i<data.length;i++){
-
pq.insert(data[i]);
-
}
-
while(!pq.isEmpty()){
-
System.out.println(pq.delMax());
-
}
-
}
- }
来自 “ ITPUB博客 ” ，链接：https://blog.itpub.net/29254281/viewspace-2125325/ ，如需转载，请注明出处，否则将追究法律责任。
上一篇：
快速排序
下一篇：
三向切分的快速排序和优化
请登录后发表评论
登录
全部评论
