一、基本概念

看似是队列，底层是基于堆实现的。按照元素间的优先级大小，进行动态的出入队。

二、实现优先级队列

import myQueue.Queue;
import myheap.MaxHeap;
/**
 * 基于最大堆实现的优先级队列
 */
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();
    }
}

三、java.util.PriorityQueue

// JDK下的优先级队列是基于最小堆实现的
Queue<Integer> queue1 = new PriorityQueue<>();
// 元素操作
queue1.offer(1); // 入队
queue1.poll(); // 出队
queue1.peek(); // 返回队首元素(最小值)

// 改造：如果想使用基于最大堆的优先级队列可以这样改
Queue<Integer> queue2 = new PriorityQueue<>(new Comparator<Integer>() {
          
   
    @Override
    public int compare(Integer o1, Integer o2) {
          
   
        return o2 - o1;
    }
});

四、TopK问题

优先级队列的应用场景：

最小或最大的k个元素 =》都是优先级队列 (堆的应用)  找最小的k个数，就构造最大堆。  找最大的k个数，就构造最小堆。 原因：  当你需要找k个较小的数时，你的最大堆顶部一定是堆中最大的元素。当遍历完所有元素时，堆顶的元素相比其它元素已经算是较小的元素了，那么堆中的其它元素一定更小。这样就有效地筛选出k个小值了。

leetCode题：

面试题17.14.最小K个数

class Solution {
          
   
    public int[] smallestK(int[] arr, int k) {
          
   
        if(arr.length == 0 || k == 0) {
          
   
            return new int[0];
        }
        int[] ret = new int[k];
        Queue<Integer> queue = new PriorityQueue<>(new Comparator<Integer>() {
          
   
            @Override
            public int compare(Integer o1, Integer o2) {
          
   
                return o2 - o1;
            }
        });
        for(int i = 0; i < arr.length; i ++) {
          
   
            if(queue.size() < k){
          
   
                queue.offer(arr[i]);
            } else if(arr[i] < queue.peek()){
          
   
                queue.poll();
                queue.offer(arr[i]);
            }
        }
        // 此时队列中存着的就是最小的k个数
        for(int i = ret.length - 1; i >= 0; i --){
          
   
            ret[i] = queue.poll();
        }
        return ret;
    }
}

总结: 提示：这里对文章进行总结： 以上就是今天的学习内容，本文是Java数据结构的学习，认识了优先级队列，如何自己实现，JDK下的优先级队列用法，以及在TopK问题中的应用。之后的学习内容将持续更新！！！