Leetcode刷题100天—优先队列介绍—day12

深碍√TFBOYSˉ_ 2022-09-10 10:24 190阅读 0赞

前言：

> 作者：神的孩子在歌唱
> 
> 大家好，我叫小智

## 介绍 ##

优先级队列也是个队列，因此也是提供以下接口

int size(); // 元素的数量
    boolean isEmpty(); // 是否为空
    void enQueue(E element); // 入队
    E deQueue(); // 出队
    E front(); // 获取队列的头元素
    void clear(); // 清空

*  普通的队列是 **FIFO** 原则，也就是先进先出
 *  优先级队列则是按照**优先级高低**进行出队，比如将**优先级最高**的元素作为**队头**优先出队

![image-20210817111801600][]

## 用例 ##

**医院的夜间门诊**

*  队列元素是病人
 *  优先级是病情的严重情况、挂号时间

**操作系统的多任务调度**

*  队列元素是任务
 *  优先级是任务类型

## **优先队列的底层实现** ##

1.  根据优先队列的特点，很容易想到：可以直接利用**二叉堆**作为**优先队列**的底层实现
2.  可以通过 **Comparator** 或 **Comparable** 去自定义优先级高低

![image-20210817132444459][]

## 作业 ##

*  数组中的第K个最大元素：https://leetcode-cn.com/problems/kth-largest-element-in-an-array/
 *  根据字符出现频率排序：https://leetcode-cn.com/problems/sort-characters-by-frequency/
 *  数据流中的第K大元素：https://leetcode-cn.com/problems/kth-largest-element-in-a-stream/
 *  有序矩阵中第K小的元素：https://leetcode-cn.com/problems/kth-smallest-element-in-a-sorted-matrix/
 *  前K个高频元素：https://leetcode-cn.com/problems/top-k-frequent-elements/
 *  前K个高频单词：https://leetcode-cn.com/problems/top-k-frequent-words/
 *  查找和最小的K对数字：https://leetcode-cn.com/problems/find-k-pairs-with-smallest-sums/
 *  合并K个排序链表：https://leetcode-cn.com/problems/merge-k-sorted-lists/

> 本人csdn博客：https://blog.csdn.net/weixin\_46654114
> 
> 转载说明：跟我说明，务必注明来源，附带本人博客连接。

[image-20210817111801600]: /images/20220829/5f130a4f814647d39c7d6741ca049669.png
[image-20210817132444459]: /images/20220829/c3ae8779a0aa48f4b7ef2ae7be3986ce.png