優(yōu)先級(jí)隊(duì)列概念
前面介紹過(guò)隊(duì)列斗搞，隊(duì)列是一種先進(jìn)先出(FIFO)的數(shù)據(jù)結(jié)構(gòu)指攒，但有些情況下，操作的數(shù)據(jù)可能帶有優(yōu)先級(jí)僻焚，一般出隊(duì)列時(shí)允悦，可能需要優(yōu)先級(jí)高的元素先出隊(duì)列，該中場(chǎng)景下虑啤，使用隊(duì)列顯然不合適隙弛，比如：在手機(jī)上玩游戲的時(shí)候，如果有來(lái)電狞山，那么系統(tǒng)應(yīng)該優(yōu)先處理打進(jìn)來(lái)的電話全闷。在這種情況下，我們的數(shù)據(jù)結(jié)構(gòu)應(yīng)該提供兩個(gè)最基本的操作萍启，一個(gè)是返回最高優(yōu)先級(jí)對(duì)象总珠，一個(gè)是添加新的對(duì)象。這種數(shù)據(jù)結(jié)構(gòu)就是優(yōu)先級(jí)隊(duì)列(Priority Queue)
PriorityQueue的特性
Java集合框架中提供了PriorityQueue和PriorityBlockingQueue兩種類型的優(yōu)先級(jí)隊(duì)列勘纯，PriorityQueue是線程不安全的局服，PriorityBlockingQueue是線程安全的，本文主要介紹PriorityQueue驳遵。
使用PriorityQueue注意事項(xiàng)：
- 使用PriorityQueue必須要導(dǎo)PriorityQueue所在的包
import.java.util.PriorityQueue;
- PriorityQueue所插入的元素必須要能比較大小淫奔，否則會(huì)拋出異常ClassCastExcepetion異常
- 不能插入null對(duì)象，否則會(huì)拋出NullPointerException
- 沒(méi)有容量限制堤结，可以插入任意個(gè)元素唆迁，會(huì)自動(dòng)擴(kuò)容
- 插入和刪除元素的時(shí)間復(fù)雜度為 o(log2N)
- PriorityQueue底層使用了堆數(shù)據(jù)結(jié)構(gòu)
優(yōu)先級(jí)隊(duì)列的構(gòu)造
| 構(gòu)造器 | 功能介紹 |
|---|---|
| PriorityQueue() | 創(chuàng)建一個(gè)空的優(yōu)先級(jí)隊(duì)列，默認(rèn)容量是11 |
| PriorityQueue(int initialCapacity) | 創(chuàng)建一個(gè)初始容量為initialCapacity的優(yōu)先級(jí)隊(duì)列竞穷，注意：initialCapacity不能小于1唐责，否則會(huì)拋IllegalArgumentExcepetion |
import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;
public class Demo {
public static void main(String[] args) {
//創(chuàng)建一個(gè)空的優(yōu)先級(jí)隊(duì)列，默認(rèn)容量是11
PriorityQueue<Integer> q1 = new PriorityQueue<>();
//創(chuàng)建一個(gè)容量為100的空優(yōu)先級(jí)隊(duì)列
PriorityQueue<Integer> q2 = new PriorityQueue<>(100);
List<Integer> list = new ArrayList<>();
list.add(1);
list.add(2);
list.add(5);
PriorityQueue<Integer> q3 = new PriorityQueue<>(list);
System.out.println(q3.size());
System.out.println(q3.peek());
}
}
image.png
插入来庭、刪除妒蔚、獲取優(yōu)先級(jí)最高的元素
| 函數(shù)名 | 功能介紹 |
|---|---|
| boolean offer(E e) | 插入元素，插入成功返回true，若e為null肴盏，會(huì)拋出NullPointerException異常科盛，時(shí)間復(fù)雜度為O(log2N)，注意若空間不夠會(huì)自動(dòng)擴(kuò)容 |
| E peek() | 獲取優(yōu)先級(jí)最高的元素菜皂，若隊(duì)列為空贞绵，則返回null |
| E poll() | 移除優(yōu)先級(jí)最高的元素，若隊(duì)列為空恍飘，則返回null |
| int size() | 獲取有效元素個(gè)數(shù) |
| void clear() | 清空 |
| boolean isEmpty() | 檢查優(yōu)先級(jí)隊(duì)列是否為空榨崩，若為空，則返回true |
package xsk;
import org.omg.CORBA.ARG_OUT;
import javax.sound.midi.Soundbank;
import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;
public class Demo {
public static void main(String[] args) {
//創(chuàng)建一個(gè)空的優(yōu)先級(jí)隊(duì)列章母，默認(rèn)容量是11
PriorityQueue<Integer> q1 = new PriorityQueue<>();
//創(chuàng)建一個(gè)容量為100的空優(yōu)先級(jí)隊(duì)列
PriorityQueue<Integer> q2 = new PriorityQueue<>(100);
List<Integer> list = new ArrayList<>();
list.add(1);
list.add(2);
list.add(5);
PriorityQueue<Integer> q3 = new PriorityQueue<>(list);
System.out.println(q3.size());
System.out.println(q3.peek());
q3.poll();
System.out.println(q3.size());
System.out.println(q3.peek());
q3.clear();
if(q3.isEmpty()) {
System.out.println("隊(duì)列為空");
} else {
System.out.println("隊(duì)列不為空");
}
q3.offer(1);
System.out.println(q3.peek());
System.out.println(q3.peek());
}
}
堆
堆是一種特殊的二叉樹：
- 堆是一個(gè)完全二叉樹
- 堆采用順序存儲(chǔ)的方式
-
堆中任一結(jié)點(diǎn)都滿足比子節(jié)點(diǎn)的值大（大堆）或比子節(jié)點(diǎn)的值心钢搿（小堆）
我們來(lái)看一個(gè)大堆在內(nèi)存的存儲(chǔ)方式
image.png
image.png
從上圖可以看出，父結(jié)點(diǎn)和子節(jié)點(diǎn)的關(guān)系：
已知父節(jié)點(diǎn)的下標(biāo)為x,則孩子節(jié)點(diǎn)的下標(biāo)：
- 左孩子下標(biāo)：2 * x + 1;
- 右孩子下標(biāo)：2 * x + 2;
已知孩子下標(biāo)為x,則父節(jié)點(diǎn)的下標(biāo)為：
- 左孩子下標(biāo)為x 時(shí)乳怎，父節(jié)點(diǎn)的下標(biāo)：( x - 1 ) / 2;
- 右孩子下標(biāo)為x時(shí)彩郊，父節(jié)點(diǎn)的下標(biāo)：( x - 1 ) / 2 或 ( x - 2 ) / 2;
堆的向下調(diào)整
image.png
仔細(xì)觀察上圖后發(fā)現(xiàn)：根節(jié)點(diǎn)的左右子樹已經(jīng)完全滿足堆的性質(zhì)，因此只需將根節(jié)點(diǎn)向下調(diào)整好即可蚪缀。
向下過(guò)程(以小堆為例)：
- 1. 讓parent標(biāo)記需要調(diào)整的節(jié)點(diǎn)秫逝，child標(biāo)記parent的左孩子(注意：parent如果有孩子一定先是有左孩子)
-
2. 如果parent的左孩子存在，即:child < size询枚， 進(jìn)行以下操作违帆，直到parent的左孩子不存在：
- parent右孩子是否存在，存在找到左右孩子中最小的孩子金蜀，讓child進(jìn)行比較
-
將parent與較小的孩子child比較刷后，如果：
* parent小于較小的孩子child，調(diào)整結(jié)束
* 否則：交換parent與較小的孩子child廉油，交換完成之后惠险，parent中大的元素
向下移動(dòng)，可能導(dǎo)致子樹不滿足堆的性質(zhì)抒线，因此需要繼續(xù)向下調(diào)整，即
parent = child; child = parent * 2 + 1;然后繼續(xù)2的過(guò)程
向下調(diào)整（小堆）：
public void shiftDown(int[] arr, int size, int index) {
int parent = index;
int child = 2 * parent + 1;
while(child < size) {
if (child + 1 < size && arr[child + 1] < arr[child]) {
child = child + 1;
}
if(arr[parent] > arr[child]) {
int tmp = arr[child];
arr[child] = arr[parent];
arr[parent] = tmp;
} else {
break;
}
parent = child;
child = 2 * parent + 1;
}
}
}
注意：在調(diào)整以parent為根的二叉樹時(shí)渣慕，必須要滿足parent的左子樹和右子樹已經(jīng)是堆了才可以向下調(diào)整嘶炭。
堆的創(chuàng)建
public static void createHeap(int[] array) {
// 找倒數(shù)第一個(gè)非葉子節(jié)點(diǎn)，從該節(jié)點(diǎn)位置開始往前一直到根節(jié)點(diǎn)逊桦，遇到一個(gè)節(jié)點(diǎn)眨猎，應(yīng)用向下調(diào)整
for(int i = arr.length - 1; i >= 0; i--) {
shiftDown(arr, arr.length, i);
}
}
堆的插入
插入堆需要兩個(gè)步驟
- 先將元素放在底層空間中
-
將最后放入的元素向上調(diào)整，直到滿足堆的性質(zhì)
public class MyPriorityQueue {
public static void shiftUp(int[] arr, int size, int index) {
int child = index;
int parent = (child - 1) / 2;
while(child > 0) {
if(arr[child] > arr[parent]) {
int tmp = arr[child];
arr[child] = arr[parent];
arr[parent] = tmp;
} else {
break;
}
child = parent;
parent = (child - 1) / 2;
}
}
public static void creatHeap(int[] arr) {
for(int i = arr.length - 1; i >= 0; i--) {
shiftUp(arr, arr.length, i);
}
}
public int[] arr = new int[100];
public int size = 0;
public void offer(int val) {
if(size >= arr.length) {
return;
}
arr[size] = val;
size++;
shiftUp(arr, size, size - 1);
}
}
堆的刪除
注意：堆刪除的一定是堆頂元素强经，具體操作如下：
- 將堆頂元素與堆的最后一個(gè)元素交換
- 堆中有效數(shù)據(jù)個(gè)數(shù)減一
-
堆頂元素進(jìn)行向下調(diào)整
image.png
public void poll(int val) {
if(size == 0) {
return;
}
int result = arr[0];
arr[0] = arr[size - 1];
arr[size - 1] = result;
size--;
shiftUp(arr, size, 0);
}
用堆實(shí)現(xiàn)優(yōu)先級(jí)隊(duì)列
package xsk;
public class MyPriorityQueue {
public static void shiftUp(int[] arr, int size, int index) {
int child = index;
int parent = (child - 1) / 2;
while(child > 0) {
if(arr[child] > arr[parent]) {
int tmp = arr[child];
arr[child] = arr[parent];
arr[parent] = tmp;
} else {
break;
}
child = parent;
parent = (child - 1) / 2;
}
}
public static void creatHeap(int[] arr) {
for(int i = arr.length - 1; i >= 0; i--) {
shiftUp(arr, arr.length, i);
}
}
public int[] arr = new int[100];
public int size = 0;
public void offer(int val) {
if(size >= arr.length) {
return;
}
arr[size] = val;
size++;
shiftUp(arr, size, size - 1);
}
public void poll(int val) {
if(size == 0) {
return;
}
int result = arr[0];
arr[0] = arr[size - 1];
arr[size - 1] = result;
size--;
shiftUp(arr, size, 0);
}
public Integer peek() {
if(size == 0) {
return null;
}
return arr[0];
}
}
