Java數(shù)據(jù)結(jié)構(gòu)之優(yōu)先級隊列(PriorityQueue)用法詳解
概念
優(yōu)先級隊列是一種先進先出（FIFO）的數(shù)據(jù)結(jié)構(gòu)，與隊列不同的是，操作的數(shù)據(jù)帶有優(yōu)先級，通俗的講就是可以比較大小，在出隊列的時候往往需要優(yōu)先級最高或者最低的元素先出隊列，這種數(shù)據(jù)結(jié)構(gòu)就是優(yōu)先級隊列（PriorityQueue）
PriorityQueue的使用
構(gòu)造方法
這里只介紹三種常用的構(gòu)造方法
| 構(gòu)造方法 | 說明 |
| PriorityQueue() | 不帶參數(shù)，默認容量為11 |
| PriorityQueue(int initialCapacity) | 參數(shù)為初始容量，該初始容量不能小于1 |
| PriorityQueue(Collection<? extends E> c) | 參數(shù)為一個集合 |
代碼展示：
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<>(); //容量默認為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)先
// 級隊列
}
}
常用方法
| 方法 | 說明 |
| boolean offer(E e) | 插入元素e，返回是否插入成功，e為null，會拋異常 |
| E peek() | 獲取堆（后面介紹堆）頂元素，如果隊列為空，返回null |
| E poll() | 刪除堆頂元素并返回，如果隊列為空，返回null |
| int size() | 獲取有效元素個數(shù) |
| void clear() | 清空隊列 |
| boolean isEmpty() | 判斷隊列是否為空 |
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的時候，報了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é)果：
默認是小堆，所以堆頂元素是1，獲取到1，在刪除1，剩余元素個數(shù)為兩個，當隊列為空的時候，這兩個方法都返回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é)果：
打印元素個數(shù)為3，所以不為空輸出false，清空后，隊列為空，輸出true
注意事項
PriorityQueue中存放的元素必須能比較大小，不能比較大小的對象不能插入，會拋出ClassCastException異常
例如：向優(yōu)先級隊列中插入兩個學生類型的數(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é)果：報了類型轉(zhuǎn)換異常的錯誤，因為student類型不能直接比較大小
如果想比較兩個自定類型的大小，請參考Java中對象的比較這篇文章
- 不能插入null對象，否則會拋NullPointerException異常
- 內(nèi)部可以自動擴容
- PriorityQueue底層使用堆數(shù)據(jù)結(jié)構(gòu)
- PriorityQueue默認是小堆，如果想要創(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的擴容方式
以下是JDK1.8中擴容的方式：
說明：
- 如果容量小于64，按照oldCapacity的2倍擴容
- 如果容量大于等于64，按照oldCapacity的1.5倍擴容
- 如果容量超過MAX_ARRAY_SIZE，按照MAX_ARRAY_SIZE擴容
小試牛刀（最小k個數(shù)）
題目
方法：創(chuàng)建一個優(yōu)先級隊列，獎數(shù)組中的元素依次放入該優(yōu)先級隊列中，在依次從該優(yōu)先級隊列取出k個即可
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)，堆其實就是對完全二叉樹的元素作出了一些調(diào)整
所謂堆就是將一組數(shù)據(jù)按照完全二叉樹的順序存儲方式存儲，保證每一個根結(jié)點元素大于它的孩子結(jié)點的元素（大根堆）或者小于它的孩子結(jié)點的元素（小根堆）
堆的性質(zhì)
堆中某個結(jié)點的值總是不大于或著不小于其父節(jié)點的值
堆是一顆完全二叉樹
堆的創(chuàng)建
此處我們創(chuàng)建小堆，以21，15，19，17，18，23，25為例
發(fā)現(xiàn)上述序列根的左右子樹都已經(jīng)滿足小堆的特性，故只需要將根結(jié)點向下調(diào)整即可
向下調(diào)整的過程：
1. 用parent標記要被調(diào)整的結(jié)點，child標記parent的左孩子
2. 如果左孩子存在，即child<size,size為序列元素的個數(shù)，進行以下操作，直到左孩子不存在
- 判斷parent右孩子是否存在，如果存在讓child標記兩個孩子最小的孩子
- 如果parent小于child，則將parent與child標記的元素交換位置，如果parent大于child，說明此時已經(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為根的二叉樹時，必須滿足parent的左右子樹滿足堆的特性，此時才能向下調(diào)整parent
時間復雜度分析：最壞情況從根比到葉子，比較的次數(shù)為二叉樹的高度，故時間復雜度為O(log2N)
那么對于普通的序列如1，5，3，8，7，6，即根節(jié)點的左右子樹不滿足大堆的特性，該如何調(diào)整？
方法：從倒數(shù)第一個非葉子結(jié)點開始調(diào)整，直到調(diào)整到根
代碼展示：
public void createHeap(int[] array){
int root = (array.length-2)>>1;
for(;root>=0;root--){
shiftDown(array,root);
}
}
創(chuàng)建堆的時間復雜度
故建堆的時間復雜度為O(N)
堆的插入
堆的插入分為兩步：
- 將元素插入隊列尾部，如果空間不夠需要擴容
- 將新插入的結(jié)點向上調(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;
}
}
}
堆的刪除
堆刪除的是堆頂元素
刪除步驟：
- 交換堆頂與堆最后一個元素的位置
- 將堆中的有效元素個數(shù)減少一個
- 將堆頂元素向下調(diào)整
代碼展示：
public int poll(){
int oldVal = array[0];
array[0] = array[array.length-1];
size--;
shiftDown(array,0);
return oldVal;
}
優(yōu)先級隊列的模擬實現(xiàn)
此處用小堆實現(xiàn)優(yōu)先級隊列，并且隊列中保存的元素為Integer類型
準備工作包括：構(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);
}
}
注意：插入前需要判斷是否擴容，此處擴容按照2倍方式擴容
刪除
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;
}
獲取有效元素個數(shù)
public int size(){
return size;
}
判空
public boolean isEmpty(){
return size==0;
}
清空
public void clear(){
size = 0;
}
堆的應用
- PriorityQueue的實現(xiàn)，PriorityQueue底層采用堆數(shù)據(jù)結(jié)構(gòu)實現(xiàn)的
- 堆排序，詳見基本排序算法總結(jié)(Java實現(xiàn))
- Top-k問題
Top-k問題
即求數(shù)據(jù)中前k個最大或者最小元素，一般情況下數(shù)據(jù)量都會比較大
如果數(shù)據(jù)量大使用排序那種方法就不可取了，那么如何解決呢？
1. 使用數(shù)據(jù)中前k個數(shù)據(jù)建堆
求前k個最大，建小堆
求前k個最小，建大堆
2. 用剩余的元素依次與堆頂元素比較
求前k個最大，若比堆頂元素大，則替換小堆堆頂元素
求前k個最小，若比堆頂元素小，則替換大堆堆頂元素
以上就是Java數(shù)據(jù)結(jié)構(gòu)之優(yōu)先級隊列(PriorityQueue)用法詳解的詳細內(nèi)容，更多關于Java優(yōu)先級隊列的資料請關注腳本之家其它相關文章！
相關文章
spring使用aspect注解切面不起作用的排查過程及解決
這篇文章主要介紹了spring使用aspect注解切面不起作用的排查過程及解決方案，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2021-06-06
這篇文章主要介紹了Java編程實現(xiàn)漢字按字母順序排序的方法,結(jié)合具體實例形式分析了java編碼轉(zhuǎn)換及字母排序相關操作技巧,需要的朋友可以參考下2017-07-07
這篇文章主要介紹了詳解JavaEE中Apollo安裝與使用，本文給大家介紹的非常詳細，對大家的學習或工作具有一定的參考借鑒價值,需要的朋友可以參考下2022-03-03
Spring Boot中進行 文件上傳和 文件下載功能實現(xiàn)
開發(fā)Wb應用時,文件上傳是很常見的一個需求,瀏覽器 通過 表單形式 將 文件 以 流的形式傳遞 給 服務器,服務器再對上傳的數(shù)據(jù)解析處理,下面將通過一個案例講解使用 SpringBoot 實現(xiàn) 文件上傳,感興趣的朋友一起看看吧2024-07-07
intelliJ idea 2023 配置Tomcat 8圖文教程
這篇文章主要介紹了intelliJ idea 2023 配置Tomcat 8教程,本文通過圖文并茂的形式給大家介紹的非常詳細，對大家的學習或工作具有一定的參考借鑒價值，需要的朋友可以參考下2023-06-06
SpringBoot使用Aspect切面攔截打印請求參數(shù)的示例代碼
這篇文章主要介紹了SpringBoot使用Aspect切面攔截打印請求參數(shù),本文通過實例代碼給大家介紹的非常詳細，對大家的學習或工作具有一定的參考借鑒價值，需要的朋友可以參考下2021-07-07
這篇文章主要為大家分享了最有價值的三道網(wǎng)絡編程面試題，涵蓋內(nèi)容全面，包括數(shù)據(jù)結(jié)構(gòu)和算法相關的題目、經(jīng)典面試編程題等，感興趣的小伙伴們可以參考一下2021-07-07
這篇文章主要介紹了Spring Boot 中的靜態(tài)資源到底要存放哪里，很多童鞋對這個問題很糾結(jié)，接下來通過本文給大家介紹下,需要的朋友可以參考下2019-04-04
這篇文章主要介紹了SpringBoot全局異常處理與定制404頁面的相關資料,本文通過實例代碼圖文相結(jié)合給大家介紹的非常詳細，需要的朋友可以參考下2007-09-09
IntelliJ IDEA中Scala、sbt、maven配置教程
這篇文章主要介紹了IntelliJ IDEA中Scala、sbt、maven配置教程，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2020-09-09