特征

和入队顺序无关，总是优先级最高的元素优先出队。
如果说栈是每次输出最近进入的元素，队列是每次输出最早进入的元素，那么优先队列就是每次输出优先级最高的元素。

API

优先队列是一种抽象数据类型，他表示了一组值和对这些值的一些操作。我们不一定要用某种固定的存储和操作方式来实现它，只要满足它的特征那它就是优先队列。但怎样才能高效实现它呢？先列出一份API：

实现逻辑

数据结构二叉堆就能很高效的实现这份API。
（堆：当一棵二叉树的某个节点都大于等于它的两个子节点时，它被称为堆有序。）
当有新元素入队时，就把它放入堆的末尾，然后让他自由上浮，直到浮到堆顶或不大于父节点的位置。

//添加一个元素
public void insert(T a){
    maxPQ.add(a);
    swim(maxPQ.size()-1);
}
//上浮
private void swim(int idx){
    int fidx = (idx-1)/2;
    if(idx==0||maxPQ.get(fidx).compareTo(maxPQ.get(idx)) >= 0)return;
    Collections.swap(maxPQ,fidx,idx);
    swim(fidx);
}

//删除并返回最大元素
public T delmax(){
    if(maxPQ.isEmpty())return null;
    Collections.swap(maxPQ,0,maxPQ.size()-1);
    T max = maxPQ.get(maxPQ.size()-1);
    maxPQ.remove(maxPQ.size()-1);
    if(maxPQ.isEmpty()==false)sink(0);
    return max;
}
//下沉
private void sink(int idx){
    int lastIdx = idx*2+1;
    if(idx<0||idx>=maxPQ.size()||lastIdx>=maxPQ.size())return;
    //如果有右节点且右节点大于左节点
    if(lastIdx<maxPQ.size()-1&&maxPQ.get(lastIdx).compareTo(maxPQ.get(lastIdx+1))<0)lastIdx++;
    if(maxPQ.get(idx).compareTo(maxPQ.get(lastIdx))>=0)return;      //如果大于所有子节点就不下沉了
    Collections.swap(maxPQ,idx,lastIdx);
    sink(lastIdx);
}

完整实现代码

import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.Comparator;

//用堆实现优先队列
public class MaxPQUseArray<T extends Comparable>{
    private ArrayList<T> maxPQ;
    MaxPQUseArray(){maxPQ = new ArrayList<>();}
    //创建一个初始容量为max的优先队列
    MaxPQUseArray(int max){maxPQ = new ArrayList<>();maxPQ.ensureCapacity(max);}
    //用数组初始化优先队列
    MaxPQUseArray(T[] arr){
        maxPQ = new ArrayList<>();
        for(T t:arr){
            insert(t);
        }
    }
    //添加一个元素
    public void insert(T a){
        maxPQ.add(a);
        swim(maxPQ.size()-1);
    }
    //返回最大元素
    public T max(){
        return maxPQ.isEmpty()?null:maxPQ.get(0);
    }
    //删除并返回最大元素
    public T delmax(){
        if(maxPQ.isEmpty())return null;
        Collections.swap(maxPQ,0,maxPQ.size()-1);
        T max = maxPQ.get(maxPQ.size()-1);
        maxPQ.remove(maxPQ.size()-1);
        if(maxPQ.isEmpty()==false)sink(0);
        return max;
    }
    //上浮
    private void swim(int idx){
        int fidx = (idx-1)/2;
        if(idx==0||maxPQ.get(fidx).compareTo(maxPQ.get(idx)) >= 0)return;
        Collections.swap(maxPQ,fidx,idx);
        swim(fidx);
    }
    //下沉
    private void sink(int idx){
        int lastIdx = idx*2+1;
        if(idx<0||idx>=maxPQ.size()||lastIdx>=maxPQ.size())return;
        //如果有右节点且右节点大于左节点
        if(lastIdx<maxPQ.size()-1&&maxPQ.get(lastIdx).compareTo(maxPQ.get(lastIdx+1))<0)lastIdx++;
        if(maxPQ.get(idx).compareTo(maxPQ.get(lastIdx))>=0)return;      //如果大于所有子节点就不下沉了
        Collections.swap(maxPQ,idx,lastIdx);
        sink(lastIdx);
    }
    public boolean isEmpty(){
        return maxPQ.isEmpty();
    }
}

测试用例

当用一个乱序的数组初始化优先队列，然后再依次输出，输出的元素顺序就是有序的了,这也就是著名的堆排序过程。

public static void main(String[] args) {
    Integer[] arr = {2,9,5,1,0,3,6,8,4,7};
    MaxPQUseArray<Integer> maxPQUseArray = new MaxPQUseArray<Integer>(arr);
    while(maxPQUseArray.isEmpty()==false){
        System.out.print(maxPQUseArray.delmax()+" ");
    }
}

输出结果
9 8 7 6 5 4 3 2 1 0

当然在大部分语言的标准库中也有写好的优先队列。

Java

API

测试样例

import java.util.Arrays;
import java.util.PriorityQueue;

public class PriorityQueueDemo {
    public static void main(String[] args) {
        Integer[] arr = {2,5,3,3,8,1,9,6,7,4};
        PriorityQueue<Integer> pque = new PriorityQueue<Integer>(Arrays.asList(arr));
        pque.add(0);
        pque.remove(3);
        System.out.println("size:"+pque.size());
        while(pque.isEmpty()==false){
            System.out.print(pque.poll()+" ");
        }
    }
}

结果

size:10
0 1 2 3 4 5 6 7 8 9

c++

API

测试样例

#include<iostream>
#include<queue>

using namespace std;

int main(){
    int arr[] = {2,6,5,4,1,7,9,8,3};
    priority_queue<int> pque(begin(arr),end(arr));
    pque.push(0);
    cout << "size:" << pque.size() << endl;
    while(!pque.empty()){
        int top = pque.top();
        pque.pop();
        cout << top << " ";
    }

    return 0;
}

结果

size:10
9 8 7 6 5 4 3 2 1 0