【详解】优先级队列的底层实现

1. 优先级队列（堆）概念

优先级队列：底层是基于堆的实现，按照优先级的大小动态出队（动态指的是元素个数动态变化，而非固定）。

普通队列：FIFO。按照元素的入队顺序出队，先入先出。

普通队列和优先级队列比较：

优先级在现实中的体现：

• 1.1医院有一群排队就医的病人，但他们的病情都是较轻的，忽然医院来了一个病情危急的病人，此时，医生会优先救治病情危急的病人；
• 1.2操作系统的任务管理器，排在前面的就是优先级高的任务

2. 二叉堆

堆本质上是一颗完全二叉树，基于最大堆实现的优先级队列，堆顶元素就是当前队列中的最大值，每次出队操作，就从堆顶取出最值，就实现了出队的优先级（JDK中的优先级队列是基于最小堆实现的）。

二叉堆的特点：

• 1.是一颗完全二叉树，使用顺序表存储，根节点从0开始，当前节点编号为k，则：

节点间的关系：
左子树节点：2K+1
右子树节点：2k+2
父节点索引：(k-1)/2

• 2.最大堆中，所有节点的值大于其左右孩子节点的值；

下面，自定义实现一个最大堆：

import java.util.ArrayList;
import java.util.List;
import java.util.NoSuchElementException;

/** * 最大堆问题 * 1.最大堆首先再结构上和满二叉树相似 * 2.最大堆满足：根节点值 >= 子节点的值 * 根节点从0开始 */
public class MaxHeap {
    
    //使用动态数组存储最大堆
    List<Integer> data;
    public MaxHeap(){
    
        //构造方法的this的调用，默认初始大小为10
        this(10);
    }

    //初始化堆大小
    public MaxHeap(int size){
    
        data  = new ArrayList<>(10);
    }

    //判空方法
    public  boolean isEmpty(){
    
        return data.size() == 0;
    }

    //根据索引得到父节点的索引
    private int parent(int k){
    
        return (k-1) >>1;
    }

    //根据索引获得左子树索引
    private  int leftChild(int k){
    
        return (k<<1)+1;            //相当于2k+1
    }
    //根据索引获得右子树索引
    private  int rightChild(int k){
    
        return (k<<1)+2;            //相当于2k+2
    }
    /** * 向堆中添加元素 * @param val */
    public void add(int val){
    
        //1.直接在堆尾添加元素
        data.add(val);          //list.add() 默认是尾插
        //2.进行元素的上浮操作
        siftUp(data.size() -1);
    }

    /** * 元素上浮操作 * @param k */
    private void siftUp(int k ){
    
        //上浮的终止条件：已经走到根节点 || 当前节点值 >=父节点值
        //循环的迭代条件 ： 还存在父节点值并且当前节点值 > 父节点值
        //k> 0 表示还没有走到父节点位置
        while ( k >0 && data.get(k) > data.get(parent(k))){
    
            //交换当前节点值和父节点值
            swap(k,parent(k));
            k = parent(k);
        }
    }

    //交换节点值
    private void swap(int i, int j) {
    
          int temp = data.get(i);
          data.set(i,data.get(j));
          data.set(j,temp);
    }
    /** * 任意数组的堆化 * 构造方法 * @param arr */
    public MaxHeap(int[ ] arr){
    
        //初始化一个动态数组
        data = new ArrayList<>(arr.length);
        //1.先将数组中所有元素复制到data中
        for (int i :arr) {
    
            data.add(i);
        }
        //2.从最后一个非叶子开始不断元素下沉
        for (int i=parent(data.size()-1); i >= 0;i--){
    
            siftDown(i);
        }
    }

    /** * 取出堆中最大值的方法 * @param * @return */
    public int extractMax(){
    
        //取值一定要判空
        if (data.isEmpty()){
    
            throw new NoSuchElementException("heap is empty!cannot extract");
        }
        //堆顶元素就是最大值
        int max = data.get(0);
        //1.将数组末尾的元素顶到堆顶
        int lastVal = data.get(data.size()-1);
        data.set(0, lastVal);
        //2.删除数组末尾的元素
        data.remove(data.size()-1);
        //3.进行元素的下沉操作
        siftDown(0);
        return max;
    }
    /** * 元素的下沉操作 * @param k */
    private void siftDown(int k) {
    
        //还存在子树
        while (leftChild(k) < data.size()){
    
            int j= leftChild(k);
            //判断是否有右子树
            if ( j+1 < data.size() && data.get(j+1) > data.get(j)){
    
                //右子树存在且大于左子树
                j=j+1;
            }
            //此时，j就是左右子树的最大值，再和k比较
            if(data.get(k) >= data.get(j)){
    
                //当前节点值大于子树节点值，下沉结束
                break;
            }else {
    
                //交换节点值
                swap(k,j);
                k = j;
            }
        }
    }

    /** * 取出堆顶元素 * @return */
    public int peekMax(){
    
        if (isEmpty()){
    
            throw new NoSuchElementException("heap is empty!");
        }
        //堆顶元素就是最大值
        return data.get(0);
    }

    @Override
    public String toString() {
    
        return data.toString();
    }
}

3. 基于最大堆实现优先级队列

• 自定义队列的接口

public interface Queue<E> {
    

    //入队
    void offer(E val);

    //出队
    E poll();

    //返回队首元素
    E peek();

    //判断队列是否为空
    boolean isEmpty();

}

• 基于最大堆实现的优先级队列

/** * jdk中的优先级队列默认是最小堆的实现，队首元素就是当前队列的队首元素就是最小值 * 基于最大堆的优先级队列，值越大优先级越高 */
public class PriorityQueue implements Queue<Integer> {
    
    
    private MaxHeap heap;

    public PriorityQueue(){
    
        heap =new MaxHeap();
    }
    @Override
    public void offer(Integer val) {
    
        heap.add(val);
    }

    @Override
    public Integer poll() {
    
        //优先级队列中出队操作就是取出当前队列的最大值
        return heap.extractMax();
    }

    @Override
    public Integer peek() {
    
        //返回队列中的最大值
        return heap.peekMax();
    }

    @Override
    public boolean isEmpty() {
    
        return heap.isEmpty();
    }
}

4. 测试

/** * 自定义最大堆测试 */
public class PriorityQueueTest {
    
    public static void main(String[] args) {
    
        int[] data ={
    1,10,12,9,6,15,7,3,8,18};
        Queue<Integer> queue =new PriorityQueue();
        for (int i: data) {
    
            queue.offer(i);
        }
        int[] ret  =new int[data.length];
        for (int i=0;i< ret.length;i++){
    
            ret[i]=queue.poll();
        }
        System.out.println(Arrays.toString(ret));
    }
}

结果：

至此，优先级队列的实现完成，优先级队列的实际应用，请看下篇博客：
优先级队列的实际应用之TopK问题