优先队列

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;
        }
    }
}