【数据结构】优先级队列

「爱情、让人受尽委屈。」 2022-11-07 01:47 238阅读 0赞

### 优先级队列（Priority Queue） ###

*  优先级队列简介
 *   *  普通队列与优先级队列对比：
     *  优先级队列应用场景：
 *  优先队列的底层实现
 *  二叉堆实现优先级队列代码
 *  练习

# 优先级队列简介 #

优先级队列也属于队列，因此也提供以下接口：

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

![在这里插入图片描述][2021031017122412.png]

## 普通队列与优先级队列对比： ##

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

## 优先级队列应用场景： ##

*  医院的夜间门诊  
    队列元素是病人  
    优先级是病情的严重情况、挂号时间
 *  操作系统的多任务调度  
    队列元素是任务  
    优先级是任务类型

# 优先队列的底层实现 #

利用二叉堆作为优先队列的底层实现

可以通过 `Comparator` 或 `Comparable` 去自定义优先级高低  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70]

# 二叉堆实现优先级队列代码 #

利用[二叉堆][Link 1]实现优先级队列。

/**
     * 二叉堆实现优先级队列
     * @author yusael
     */
    public class PriorityQueue<E> {
        
    	private BinaryHeap<E> heap;
    	
    	// 通过 comparator 自定义优先级高低
    	public PriorityQueue(Comparator<E> comparator) {
        
    		heap = new BinaryHeap<>(comparator);
    	}
    	
    	public PriorityQueue() {
        
    		this(null);
    	}
    	
    	public int size() {
        
    		return heap.size();
    	}
    
    	public boolean isEmpty() {
        
    		return heap.isEmpty();
    	}
    	
    	public void clear() {
        
    		heap.clear();
    	}
    
    	public void enQueue(E element) {
        
    		heap.add(element);
    	}
    
    	public E deQueue() {
        
    		return heap.remove();
    	}
    
    	public E front() {
        
    		return heap.get();
    	}
    }

# 练习 #

◼ 数组中的第K个最大元素：[https://leetcode-cn.com/problems/kth-largest-element-in-an-array/][https_leetcode-cn.com_problems_kth-largest-element-in-an-array]

◼ 根据字符出现频率排序：[https://leetcode-cn.com/problems/sort-characters-by-frequency/][https_leetcode-cn.com_problems_sort-characters-by-frequency]

◼ 数据流中的第K大元素：[https://leetcode-cn.com/problems/kth-largest-element-in-a-stream/][https_leetcode-cn.com_problems_kth-largest-element-in-a-stream]

◼ 有序矩阵中第K小的元素：[https://leetcode-cn.com/problems/kth-smallest-element-in-a-sorted-matrix/][https_leetcode-cn.com_problems_kth-smallest-element-in-a-sorted-matrix]

◼ 前K个高频元素：[https://leetcode-cn.com/problems/top-k-frequent-elements/][https_leetcode-cn.com_problems_top-k-frequent-elements]

◼ 前K个高频单词：[https://leetcode-cn.com/problems/top-k-frequent-words/][https_leetcode-cn.com_problems_top-k-frequent-words]

◼ 查找和最小的K对数字：[https://leetcode-cn.com/problems/find-k-pairs-with-smallest-sums/][https_leetcode-cn.com_problems_find-k-pairs-with-smallest-sums]

◼ 合并K个排序链表：[https://leetcode-cn.com/problems/merge-k-sorted-lists/][https_leetcode-cn.com_problems_merge-k-sorted-lists]

[2021031017122412.png]: /images/20221023/4262325292864f19ade6661fd9f09bdc.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70]: /images/20221023/d8924ccdbb0441988c9f808c6f95095d.png
[Link 1]: https://blog.csdn.net/qq_32727095/article/details/114625362?spm=1001.2014.3001.5501
[https_leetcode-cn.com_problems_kth-largest-element-in-an-array]: https://leetcode-cn.com/problems/kth-largest-element-in-an-array/
[https_leetcode-cn.com_problems_sort-characters-by-frequency]: https://leetcode-cn.com/problems/sort-characters-by-frequency/
[https_leetcode-cn.com_problems_kth-largest-element-in-a-stream]: https://leetcode-cn.com/problems/kth-largest-element-in-a-stream/
[https_leetcode-cn.com_problems_kth-smallest-element-in-a-sorted-matrix]: https://leetcode-cn.com/problems/kth-smallest-element-in-a-sorted-matrix/
[https_leetcode-cn.com_problems_top-k-frequent-elements]: https://leetcode-cn.com/problems/top-k-frequent-elements/
[https_leetcode-cn.com_problems_top-k-frequent-words]: https://leetcode-cn.com/problems/top-k-frequent-words/
[https_leetcode-cn.com_problems_find-k-pairs-with-smallest-sums]: https://leetcode-cn.com/problems/find-k-pairs-with-smallest-sums/
[https_leetcode-cn.com_problems_merge-k-sorted-lists]: https://leetcode-cn.com/problems/merge-k-sorted-lists/