java描述
实现插入和删除都是对数级别的
public class MaxPQ<Key extends Comparable<Key>> {
// 基于堆的完全二叉树
private Key[] pq;
// 储存在pq[1..N], pq[0]表示没有使用
private int N = 0;
public static void main(String[] args) {
MaxPQ pq = new MaxPQ(10);
pq.insert(1);
pq.insert(2);
pq.insert(3);
pq.insert(4);
System.out.println(pq.delMax());
System.out.println(pq.delMax());
}
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);
}
public Key delMax(){
// 从根节点获取得到最大元素
Key max = pq[1];
// 将其和最后一个节点交换
exch(1, N--);
// 防止对象游离
pq[N+1] = null;
sink(1);
return max;
}
private boolean less(int i, int j){
return pq[i].compareTo(pq[j]) < 0;
}
private void exch(int i, int j){
Key temp = pq[i];
pq[i] = pq[j];
pq[j] = temp;
}
private void swim(int k){
while(k > 1 && less(k/2, k)){
exch(k/2, k);
k = k / 2;
}
}
private void sink(int k){
while(2*k <= N){
int j = 2*k;
// 找到子节点两个 找出他们最大的那个
if(j < N && less(j, j+1)){
j++;
}
// 如果pq[k] >= pq[j] 说明父节点比子节点大
if(!less(k, j)){
break;
}
exch(k, j);
k = j;
}
}
}
