Java數(shù)據(jù)結(jié)構(gòu)之優(yōu)先級隊(duì)列(PriorityQueue)用法詳解
概念
優(yōu)先級隊(duì)列是一種先進(jìn)先出（FIFO）的數(shù)據(jù)結(jié)構(gòu)，與隊(duì)列不同的是，操作的數(shù)據(jù)帶有優(yōu)先級，通俗的講就是可以比較大小，在出隊(duì)列的時(shí)候往往需要優(yōu)先級最高或者最低的元素先出隊(duì)列，這種數(shù)據(jù)結(jié)構(gòu)就是優(yōu)先級隊(duì)列（PriorityQueue）
PriorityQueue的使用
構(gòu)造方法
這里只介紹三種常用的構(gòu)造方法
| 構(gòu)造方法 | 說明 |
| PriorityQueue() | 不帶參數(shù)，默認(rèn)容量為11 |
| PriorityQueue(int initialCapacity) | 參數(shù)為初始容量，該初始容量不能小于1 |
| PriorityQueue(Collection<? extends E> c) | 參數(shù)為一個(gè)集合 |
代碼展示：
import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;
public class TestPriorityQueue {
public static void main(String[] args) {
PriorityQueue<Integer> p1 = new PriorityQueue<>(); //容量默認(rèn)為11
PriorityQueue<Integer> p2 = new PriorityQueue<>(10); //參數(shù)為初始容量
List<Integer> list = new ArrayList<>();
list.add(0);
list.add(1);
list.add(2);
PriorityQueue<Integer> p3 = new PriorityQueue<>(list); //使用集合list作為參數(shù)構(gòu)造優(yōu)先
// 級隊(duì)列
}
}
常用方法
| 方法 | 說明 |
| boolean offer(E e) | 插入元素e，返回是否插入成功，e為null，會拋異常 |
| E peek() | 獲取堆（后面介紹堆）頂元素，如果隊(duì)列為空，返回null |
| E poll() | 刪除堆頂元素并返回，如果隊(duì)列為空，返回null |
| int size() | 獲取有效元素個(gè)數(shù) |
| void clear() | 清空隊(duì)列 |
| boolean isEmpty() | 判斷隊(duì)列是否為空 |
offer方法的測試
PriorityQueue<Integer> p = new PriorityQueue<>();
p.offer(1);
p.offer(2);
p.offer(3);
System.out.println(p.size());
p.offer(null);
打印結(jié)果：
1，2，3都正常插入，但是插入null的時(shí)候，報(bào)了NullPointerException空指針異常
peek與poll方法的測試
PriorityQueue<Integer> p = new PriorityQueue<>();
p.offer(1);
p.offer(2);
p.offer(3);
System.out.println(p.peek());
System.out.println(p.poll());
System.out.println(p.size());
p.clear();
System.out.println(p.peek());
System.out.println(p.poll());
打印結(jié)果：
默認(rèn)是小堆，所以堆頂元素是1，獲取到1，在刪除1，剩余元素個(gè)數(shù)為兩個(gè)，當(dāng)隊(duì)列為空的時(shí)候，這兩個(gè)方法都返回null
size，isEmpty，clear方法的測試
PriorityQueue<Integer> p = new PriorityQueue<>();
p.offer(1);
p.offer(2);
p.offer(3);
System.out.println(p.size());
System.out.println(p.isEmpty());
p.clear();
System.out.println(p.isEmpty());
打印結(jié)果：
打印元素個(gè)數(shù)為3，所以不為空輸出false，清空后，隊(duì)列為空，輸出true
注意事項(xiàng)
PriorityQueue中存放的元素必須能比較大小，不能比較大小的對象不能插入，會拋出ClassCastException異常
例如：向優(yōu)先級隊(duì)列中插入兩個(gè)學(xué)生類型的數(shù)據(jù)
class Student {
private String name;
private int age;
public Student(String name, int age) {
this.name = name;
this.age = age;
}
}
public class Test {
public static void main(String[] args) {
Student s1 = new Student("張三",25);
Student s2 = new Student("李四",30);
PriorityQueue<Student> p = new PriorityQueue();
p.offer(s1);
p.offer(s2);
}
}
結(jié)果：報(bào)了類型轉(zhuǎn)換異常的錯(cuò)誤，因?yàn)閟tudent類型不能直接比較大小
如果想比較兩個(gè)自定類型的大小，請參考Java中對象的比較這篇文章
- 不能插入null對象，否則會拋NullPointerException異常
- 內(nèi)部可以自動(dòng)擴(kuò)容
- PriorityQueue底層使用堆數(shù)據(jù)結(jié)構(gòu)
- PriorityQueue默認(rèn)是小堆，如果想要?jiǎng)?chuàng)建大堆可以使用如下方式創(chuàng)建：
PriorityQueue<Integer> pq = new PriorityQueue<>(new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return o2-o1;
}
});
注意：o2-o1是創(chuàng)建大堆，o1-o2是創(chuàng)建小堆
PriorityQueue的擴(kuò)容方式
以下是JDK1.8中擴(kuò)容的方式：
說明：
- 如果容量小于64，按照oldCapacity的2倍擴(kuò)容
- 如果容量大于等于64，按照oldCapacity的1.5倍擴(kuò)容
- 如果容量超過MAX_ARRAY_SIZE，按照MAX_ARRAY_SIZE擴(kuò)容
小試牛刀（最小k個(gè)數(shù)）
題目
方法：創(chuàng)建一個(gè)優(yōu)先級隊(duì)列，獎(jiǎng)數(shù)組中的元素依次放入該優(yōu)先級隊(duì)列中，在依次從該優(yōu)先級隊(duì)列取出k個(gè)即可
class Solution {
public int[] smallestK(int[] arr, int k) {
int[] ret = new int[k];
if(k == 0 || arr.length==0){
return ret;
}
PriorityQueue<Integer> p = new PriorityQueue<>(arr.length);
for(int i = 0;i < arr.length;i++){
p.offer(arr[i]);
}
for(int i = 0;i < k;i++){
ret[i] = p.poll();
}
return ret;
}
}
堆的介紹
JDK1.8中PriorityQueue底層采用了堆數(shù)據(jù)結(jié)構(gòu)，堆其實(shí)就是對完全二叉樹的元素作出了一些調(diào)整
所謂堆就是將一組數(shù)據(jù)按照完全二叉樹的順序存儲方式存儲，保證每一個(gè)根結(jié)點(diǎn)元素大于它的孩子結(jié)點(diǎn)的元素（大根堆）或者小于它的孩子結(jié)點(diǎn)的元素（小根堆）
堆的性質(zhì)
堆中某個(gè)結(jié)點(diǎn)的值總是不大于或著不小于其父節(jié)點(diǎn)的值
堆是一顆完全二叉樹
堆的創(chuàng)建
此處我們創(chuàng)建小堆，以21，15，19，17，18，23，25為例
發(fā)現(xiàn)上述序列根的左右子樹都已經(jīng)滿足小堆的特性，故只需要將根結(jié)點(diǎn)向下調(diào)整即可
向下調(diào)整的過程：
1. 用parent標(biāo)記要被調(diào)整的結(jié)點(diǎn)，child標(biāo)記parent的左孩子
2. 如果左孩子存在，即child<size,size為序列元素的個(gè)數(shù)，進(jìn)行以下操作，直到左孩子不存在
- 判斷parent右孩子是否存在，如果存在讓child標(biāo)記兩個(gè)孩子最小的孩子
- 如果parent小于child，則將parent與child標(biāo)記的元素交換位置，如果parent大于child，說明此時(shí)已經(jīng)滿足小堆的特性
- 讓parent=child，child=parent*2+1，循環(huán)步驟2，直到不滿足步驟2的條件
代碼展示：
public void shiftDown(int[] array,int parent){
int child = parent*2+1;
int size = array.length;
while(child < size){
if(child+1<size && array[child]>array[child+1]){
child = child+1;
}
if(array[parent] > array[child]){
swap(array,parent,child);
parent = child;
child = parent*2+1;
}else {
break;
}
}
}
注意：在調(diào)整以parent為根的二叉樹時(shí)，必須滿足parent的左右子樹滿足堆的特性，此時(shí)才能向下調(diào)整parent
時(shí)間復(fù)雜度分析：最壞情況從根比到葉子，比較的次數(shù)為二叉樹的高度，故時(shí)間復(fù)雜度為O(log2N)
那么對于普通的序列如1，5，3，8，7，6，即根節(jié)點(diǎn)的左右子樹不滿足大堆的特性，該如何調(diào)整？
方法：從倒數(shù)第一個(gè)非葉子結(jié)點(diǎn)開始調(diào)整，直到調(diào)整到根
代碼展示：
public void createHeap(int[] array){
int root = (array.length-2)>>1;
for(;root>=0;root--){
shiftDown(array,root);
}
}
創(chuàng)建堆的時(shí)間復(fù)雜度
故建堆的時(shí)間復(fù)雜度為O(N)
堆的插入
堆的插入分為兩步：
- 將元素插入隊(duì)列尾部，如果空間不夠需要擴(kuò)容
- 將新插入的結(jié)點(diǎn)向上調(diào)整，直到滿足堆的特性
例如：給大堆8，7，6，5，1，3插入9
代碼展示：
public void shiftUp(int[] array,int child){
int parent = (child-1)/2;
while(child > 0){
if(array[child] < array[parent]){
break;
}else {
swap(array,parent,child);
child = parent;
parent = (child-1)/2;
}
}
}
堆的刪除
堆刪除的是堆頂元素
刪除步驟：
- 交換堆頂與堆最后一個(gè)元素的位置
- 將堆中的有效元素個(gè)數(shù)減少一個(gè)
- 將堆頂元素向下調(diào)整
代碼展示：
public int poll(){
int oldVal = array[0];
array[0] = array[array.length-1];
size--;
shiftDown(array,0);
return oldVal;
}
優(yōu)先級隊(duì)列的模擬實(shí)現(xiàn)
此處用小堆實(shí)現(xiàn)優(yōu)先級隊(duì)列，并且隊(duì)列中保存的元素為Integer類型
準(zhǔn)備工作包括：構(gòu)造方法，向上調(diào)整，向下調(diào)整，交換
public class MyPriorityQueue {
Integer[] array;
int size;
public MyPriorityQueue(){
array = new Integer[11];
size = 0;
}
public MyPriorityQueue(int initCapacity){
if(initCapacity < 1){
throw new IllegalArgumentException("初始容量小于1");
}
array = new Integer[initCapacity];
size = 0;
}
public MyPriorityQueue(Integer[] arr){
array = new Integer[arr.length];
for(int i = 0;i < arr.length;i++){
array[i] = arr[i];
}
size = arr.length;
int lastLeafParent = (size-2)/2;
for(int root = lastLeafParent;root >= 0;root--){
shiftDown(root);
}
}
public void shiftDown(int parent){
int child = parent*2+1;
while(child < size){
if(child+1<size && array[child+1]<array[child]){
child = child+1;
}
if(array[parent] > array[child]){
swap(parent,child);
parent = child;
child = parent*2+1;
}else {
return;
}
}
}
public void shiftUp(int child){
int parent = (child-1)/2;
while(child > 0){
if(array[child] < array[parent]){
swap(child,parent);
child = parent;
parent = (child-1)/2;
}else {
return;
}
}
}
public void swap(int a,int b){
int t = array[a];
array[a] = array[b];
array[b] = t;
}
}
插入
public boolean offer(Integer e){
if(e == null){
throw new NullPointerException("插入的元素為null");
}
ensureCapacity();
array[size++] = e;
shiftUp(size-1);
return true;
}
private void ensureCapacity(){
if(array.length == size){
int newCapacity = array.length*2;
array = Arrays.copyOf(array,newCapacity);
}
}
注意：插入前需要判斷是否擴(kuò)容，此處擴(kuò)容按照2倍方式擴(kuò)容
刪除
public Integer poll(){
if(isEmpty()){
return null;
}
Integer ret = array[0];
swap(0,size-1);
shiftDown(0);
return ret;
}
獲取堆頂元素
public Integer peek(){
if(isEmpty()){
return null;
}
Integer ret = array[0];
return ret;
}
獲取有效元素個(gè)數(shù)
public int size(){
return size;
}
判空
public boolean isEmpty(){
return size==0;
}
清空
public void clear(){
size = 0;
}
堆的應(yīng)用
- PriorityQueue的實(shí)現(xiàn)，PriorityQueue底層采用堆數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)的
- 堆排序，詳見基本排序算法總結(jié)(Java實(shí)現(xiàn))
- Top-k問題
Top-k問題
即求數(shù)據(jù)中前k個(gè)最大或者最小元素，一般情況下數(shù)據(jù)量都會比較大
如果數(shù)據(jù)量大使用排序那種方法就不可取了，那么如何解決呢？
1. 使用數(shù)據(jù)中前k個(gè)數(shù)據(jù)建堆
求前k個(gè)最大，建小堆
求前k個(gè)最小，建大堆
2. 用剩余的元素依次與堆頂元素比較
求前k個(gè)最大，若比堆頂元素大，則替換小堆堆頂元素
求前k個(gè)最小，若比堆頂元素小，則替換大堆堆頂元素
以上就是Java數(shù)據(jù)結(jié)構(gòu)之優(yōu)先級隊(duì)列(PriorityQueue)用法詳解的詳細(xì)內(nèi)容，更多關(guān)于Java優(yōu)先級隊(duì)列的資料請關(guān)注腳本之家其它相關(guān)文章！
相關(guān)文章
Spring實(shí)戰(zhàn)之設(shè)置普通屬性值的方法示例
這篇文章主要介紹了Spring實(shí)戰(zhàn)之設(shè)置普通屬性值的方法,結(jié)合實(shí)例形式分析了Spring設(shè)置普通屬性值的方法及相關(guān)操作注意事項(xiàng),需要的朋友可以參考下2019-11-11
java 中HttpClient傳輸xml字符串實(shí)例詳解
這篇文章主要介紹了java 中HttpClient傳輸xml字符串實(shí)例詳解的相關(guān)資料,需要的朋友可以參考下2017-04-04
在很多情況下，注釋配置比 XML 配置更受歡迎，注釋配置有進(jìn)一步流行的趨勢。Spring 2.5 的一大增強(qiáng)就是引入了很多注釋類，現(xiàn)在您已經(jīng)可以使用注釋配置完成大部分 XML 配置的功能2013-09-09
Java編程redisson實(shí)現(xiàn)分布式鎖代碼示例
這篇文章主要介紹了Java編程redisson實(shí)現(xiàn)分布式鎖代碼示例，小編覺得還是比較不錯(cuò)的，這里給大家分享下，供需要的朋友參考。2017-10-10
Spring?Boot集成RabbitMQ以及隊(duì)列模式操作
RabbitMQ是實(shí)現(xiàn)AMQP(高級消息隊(duì)列協(xié)議)的消息中間件的一種,下面這篇文章主要給大家介紹了關(guān)于Spring?Boot集成RabbitMQ以及隊(duì)列模式操作的相關(guān)資料,文中通過實(shí)例代碼介紹的非常詳細(xì),需要的朋友可以參考下2022-04-04
Java concurrency集合之ConcurrentSkipListSet_動(dòng)力節(jié)點(diǎn)Java學(xué)院整理
這篇文章主要為大家詳細(xì)介紹了Java concurrency集合之ConcurrentSkipListSet的相關(guān)資料，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2017-06-06
這篇文章主要為大家詳細(xì)介紹了java實(shí)現(xiàn)簡單發(fā)送郵件功能，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2022-04-04
這篇文章主要介紹了IDEA 快速返回上次查看代碼的位置的方法，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2020-08-08
這篇文章主要介紹了Java編程中if...else語句的嵌套寫法,是Java入門學(xué)習(xí)中的基礎(chǔ)知識,需要的朋友可以參考下2015-11-11
Spring Boot Maven Plugin打包異常解決方案
這篇文章主要介紹了Spring Boot Maven Plugin打包異常解決方案,文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2020-11-11