优先队列

• 应用意义
• 概念/性质
• 基本操作
• 代码实现
• 相关

应用意义

你可能有一台能够同时运行多个应用程序的电脑（或者手机）。这是通过为每个应用程序的事件分配一个优先级，并总是处理下一个优先级最高的事件来实现的。

概念/性质

• 支持两种操作--删除最大元素和插入元素的数据类型。

• 类比
  队列（删除最老的元素）
  栈（删除最新的元素）

基本操作

1. 插入元素
2. 删除最大元素

代码实现

# 由下至上的堆有序化（上浮）
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++;
        if(!less(k, j)) break;
        exch(k, j);
        k = j;
    }
}

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);
    }
    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);
    private void exch(int i, int j);
    private void swim(int k);
    private void sink(int k);
}

相关

Java系统库中的实现: java.utils.PriorityQueue