??????????個(gè)人主頁??????????
??????????數(shù)據(jù)結(jié)構(gòu)專欄??????????
??????????【數(shù)據(jù)結(jié)構(gòu)】非線性結(jié)構(gòu)——二叉樹??????????
1. 優(yōu)先級(jí)隊(duì)列
1.1 概念
前面介紹過隊(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í)候，如果有來電，那么系統(tǒng)應(yīng)該優(yōu)先處理打進(jìn)來的電話；初中那會(huì)班主任排座位時(shí)可能會(huì)讓成績(jī)好的同學(xué)先挑座位。在這種情況下，數(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)。
2. 優(yōu)先級(jí)隊(duì)列的模擬實(shí)現(xiàn)
JDK1.8中的PriorityQueue底層使用了堆這種數(shù)據(jù)結(jié)構(gòu)，而堆實(shí)際就是在完全二叉樹的基礎(chǔ)上進(jìn)行了一些調(diào)整。
2.1 堆的概念
如果有一個(gè)關(guān)鍵碼的集合K = {k0，k1， k2，…，kn-1}，把它的所有元素按完全二叉樹的順序存儲(chǔ)方式存儲(chǔ) 在一個(gè)一維數(shù)組中，并滿足：Ki <= K2i+1 且 Ki<= K2i+2 (Ki >= K2i+1 且 Ki >= K2i+2) i = 0，1，2…，則稱為 小堆(或大堆)。將根節(jié)點(diǎn)最大的堆叫做最大堆或大根堆，根節(jié)點(diǎn)最小的堆叫做最小堆或小根堆。
總結(jié)：
小根堆：父親節(jié)點(diǎn)比子結(jié)點(diǎn)小
大根堆：父親節(jié)點(diǎn)比子結(jié)點(diǎn)大
堆的性質(zhì)：
堆中某個(gè)節(jié)點(diǎn)的值總是不大于或不小于其父節(jié)點(diǎn)的值；
堆總是一棵完全二叉樹。
2.2 堆的存儲(chǔ)方式
從堆的概念可知，堆是一棵完全二叉樹，因此可以層序的規(guī)則采用順序的方式來高效存儲(chǔ)，
注意：對(duì)于非完全二叉樹，則不適合使用順序方式進(jìn)行存儲(chǔ)，因?yàn)闉榱四軌蜻€原二叉樹，空間中必須要存儲(chǔ)空節(jié)點(diǎn)，就會(huì)導(dǎo)致空間利用率比較低。
將元素存儲(chǔ)到數(shù)組中后，可以根據(jù)二叉樹章節(jié)的性質(zhì)5對(duì)樹進(jìn)行還原。假設(shè)i為節(jié)點(diǎn)在數(shù)組中的下標(biāo)，則有：
如果i為0，則i表示的節(jié)點(diǎn)為根節(jié)點(diǎn)，否則i節(jié)點(diǎn)的雙親節(jié)點(diǎn)為 (i - 1)/2
如果2 * i + 1 小于節(jié)點(diǎn)個(gè)數(shù)，則節(jié)點(diǎn)i的左孩子下標(biāo)為2 * i + 1，否則沒有左孩子
如果2 * i + 2 小于節(jié)點(diǎn)個(gè)數(shù)，則節(jié)點(diǎn)i的右孩子下標(biāo)為2 * i + 2，否則沒有右孩子
2.3 堆的創(chuàng)建
2.3.1 堆向下調(diào)整
對(duì)于集合{ 27,15,19,18,28,34,65,49,25,37 }中的數(shù)據(jù)，如果將其創(chuàng)建成堆呢？
仔細(xì)觀察上圖后發(fā)現(xiàn)：根節(jié)點(diǎn)的左右子樹已經(jīng)完全滿足堆的性質(zhì)，因此只需將根節(jié)點(diǎn)向下調(diào)整好即可。
向下過程(以小堆為例)：
- 讓parent標(biāo)記需要調(diào)整的節(jié)點(diǎn)，child標(biāo)記parent的左孩子(注意：parent如果有孩子一定先是有左孩子)
- 如果parent的左孩子存在，即:child < size， 進(jìn)行以下操作，直到parent的左孩子不存在
parent右孩子是否存在，存在找到左右孩子中最小的孩子，讓child進(jìn)行標(biāo)
將parent與較小的孩子child比較，如果：
parent小于較小的孩子child，調(diào)整結(jié)束
否則：交換parent與較小的孩子child，交換完成之后，parent中大的元素向下移動(dòng)，可能導(dǎo)致子
樹不滿足對(duì)的性質(zhì)，因此需要繼續(xù)向下調(diào)整，即parent = child；child = parent*2+1; 然后繼續(xù)2。
代碼實(shí)現(xiàn)：
//小堆創(chuàng)建
public void createSmallHeap() {
//由最后一棵子樹的結(jié)點(diǎn)找到它的父節(jié)點(diǎn)下標(biāo)，然后從這棵子樹開始向下調(diào)整，依次下標(biāo)減1.
for(int parent = (usedSize-1-1)/2;parent>=0;parent--) {
//此刻傳的兩個(gè)參數(shù)，分別為要向下調(diào)整的根結(jié)點(diǎn)的下標(biāo)和這個(gè)數(shù)組的長(zhǎng)度
//為什么傳的數(shù)組的長(zhǎng)度，因?yàn)檫@個(gè)向下調(diào)整是一個(gè)過程，它總有一個(gè)時(shí)間段是停下的，傳的這個(gè)數(shù)組長(zhǎng)度就是一個(gè)臨界條件
siftDown2(parent,usedSize);
}
}
//向下調(diào)整的方法
public void siftDown2(int p,int end) {
//得到該結(jié)點(diǎn)的子結(jié)點(diǎn)的下標(biāo)
int c = 2*p + 1;
//臨界條件：子結(jié)點(diǎn)的下標(biāo)<數(shù)組的長(zhǎng)度
while(c < end) {
//找到最小的子結(jié)點(diǎn)
if(c+1<end && elem[c] >elem[c+1]) {
c++;
}
//將該結(jié)點(diǎn)與最小子結(jié)點(diǎn)比較，如大于則交換否則直接break返回
if(elem[p] > elem[c]) {
//交換
swap(p,c);
//將指向該結(jié)點(diǎn)的引用指向該結(jié)點(diǎn)的子結(jié)點(diǎn)，再重新將子結(jié)點(diǎn)的下標(biāo)進(jìn)行變化，檢查該結(jié)點(diǎn)的子樹是否滿足大堆，不滿足則繼續(xù)向下調(diào)整
p = c;
c = 2*p + 1;
} else {
break;
}
}
}
以下是創(chuàng)建小堆完成的圖：
注意：在調(diào)整以parent為根的二叉樹時(shí)，必須要滿足parent的左子樹和右子樹已經(jīng)是堆了才可以向下調(diào)整。
時(shí)間復(fù)雜度：最壞的情況是O(log2 N)是以2為底的N的對(duì)數(shù)
大堆創(chuàng)建的代碼：
//大堆的創(chuàng)建
public void createBigHeap() {
//由最后一棵子樹的結(jié)點(diǎn)找到它的父節(jié)點(diǎn)下標(biāo)，然后從這棵子樹開始向下調(diào)整，依次下標(biāo)減1.
for(int parent = (usedSize-1-1)/2;parent>=0;parent--) {
//此刻傳的兩個(gè)參數(shù)，分別為要向下調(diào)整的根結(jié)點(diǎn)的下標(biāo)和這個(gè)數(shù)組的長(zhǎng)度
//為什么傳的數(shù)組的長(zhǎng)度，因?yàn)檫@個(gè)向下調(diào)整是一個(gè)過程，它總有一個(gè)時(shí)間段是停下的，傳的這個(gè)數(shù)組長(zhǎng)度就是一個(gè)臨界條件
siftDown1(parent,usedSize);
}
}
//向下調(diào)整的方法
public void siftDown1(int p,int end) {
//得到該結(jié)點(diǎn)的子結(jié)點(diǎn)的下標(biāo)
int c = 2*p + 1;
//臨界條件：子結(jié)點(diǎn)的下標(biāo)<數(shù)組的長(zhǎng)度
while(c < end) {
//找到最大的子結(jié)點(diǎn)
if(c+1<end && elem[c] < elem[c+1]) {
c++;
}
//將該結(jié)點(diǎn)與最大子結(jié)點(diǎn)比較，如小于則交換否則直接break返回
if(elem[p] < elem[c]) {
//交換
swap(p,c);
//將指向該結(jié)點(diǎn)的引用指向該結(jié)點(diǎn)的子結(jié)點(diǎn)，再重新將子結(jié)點(diǎn)的下標(biāo)進(jìn)行變化，檢查該結(jié)點(diǎn)的子樹是否滿足大堆，不滿足則繼續(xù)向下調(diào)整
p = c;
c = 2*p + 1;
} else {
break;
}
}
}
//交換方法
public void swap(int x, int y) {
int tmp = elem[x];
elem[x] = elem[y];
elem[y] = tmp;
}
2.4 堆的插入與刪除
2.4.1 堆的插入
堆的插入總共需要兩個(gè)步驟：
- 先將元素放入到底層空間中(注意：空間不夠時(shí)需要擴(kuò)容)
- 將最后新插入的節(jié)點(diǎn)向上調(diào)整，直到滿足堆的性質(zhì)
畫圖演示過程：
代碼實(shí)現(xiàn)：
//堆的插入
public void offer(int val) {
//1.判斷是否擴(kuò)容
if(isFull()) {
this.elem = Arrays.copyOf(elem,2*elem.length);
}
//插入元素
elem[usedSize] = val;
usedSize++;//11
//向上調(diào)整
siftUp(usedSize-1);
}
private void siftUp(int child) {
int parent = (child-1)>>>1; //>>>1等于除于2
while(child > 0) {
//判斷child與parent的大小
if(child >parent) {
//交換
swap(parent,child);
//移動(dòng)c與p的位置
child = parent;
parent = (child-1)>>>1;
} else {
break;
}
}
}
private boolean isFull() {
return usedSize == elem.length;
}
2.4.2 堆的刪除
注意：堆的刪除一定刪除的是堆頂元素。具體如下：
- 將堆頂元素對(duì)堆中最后一個(gè)元素交換
- 將堆中有效數(shù)據(jù)個(gè)數(shù)減少一個(gè)
- 對(duì)堆頂元素進(jìn)行向下調(diào)整
代碼實(shí)現(xiàn)：
//堆的刪除(堆的刪除一定是堆頂元素)
public int poll() {
//記錄刪除的元素
int tmp = elem[0];
//交換堆頂元素與最后一個(gè)元素
swap(0,usedSize-1);
//數(shù)組長(zhǎng)度減1
usedSize--;
//對(duì)堆頂元素向下調(diào)整,因?yàn)檫@個(gè)堆本身之前是一個(gè)大堆，堆頂之下的結(jié)點(diǎn)基本都滿足大堆的規(guī)則，所以只需要從堆頂?shù)脑叵蛳抡{(diào)整即可
// 直到這個(gè)堆完全滿足大堆的特性
siftDown1(0,usedSize);
return tmp;
}
//向下調(diào)整的方法
public void siftDown1(int p,int end) {
//得到該結(jié)點(diǎn)的子結(jié)點(diǎn)的下標(biāo)
int c = 2*p + 1;
//臨界條件：子結(jié)點(diǎn)的下標(biāo)<數(shù)組的長(zhǎng)度
while(c < end) {
//找到最大的子結(jié)點(diǎn)
if(c+1<end && elem[c] < elem[c+1]) {
c++;
}
//將該結(jié)點(diǎn)與最大子結(jié)點(diǎn)比較，如小于則交換否則直接break返回
if(elem[p] < elem[c]) {
//交換
swap(p,c);
//將指向該結(jié)點(diǎn)的引用指向該結(jié)點(diǎn)的子結(jié)點(diǎn)，再重新將子結(jié)點(diǎn)的下標(biāo)進(jìn)行變化，檢查該結(jié)點(diǎn)的子樹是否滿足大堆，不滿足則繼續(xù)向下調(diào)整
p = c;
c = 2*p + 1;
} else {
break;
}
}
}
3.常用接口介紹
3.1 PriorityQueue的特性
Java集合框架中提供了PriorityQueue和PriorityBlockingQueue兩種類型的優(yōu)先級(jí)隊(duì)列，PriorityQueue是線程不安全的，PriorityBlockingQueue是線程安全的，本文主要介紹PriorityQueue。
關(guān)于PriorityQueue的使用要注意：
- 使用時(shí)必須導(dǎo)入PriorityQueue所在的包，即：
import java.util.PriorityQueue;
- PriorityQueue中放置的元素必須要能夠比較大小，不能插入無法比較大小的對(duì)象，否則會(huì)拋出
ClassCastException異常 - 不能插入null對(duì)象，否則會(huì)拋出NullPointerException
- 沒有容量限制，可以插入任意多個(gè)元素，其內(nèi)部可以自動(dòng)擴(kuò)容
- 插入和刪除元素的時(shí)間復(fù)雜度為
- PriorityQueue底層使用了堆數(shù)據(jù)結(jié)構(gòu)
- PriorityQueue默認(rèn)情況下是小堆—即每次獲取到的元素都是最小的元素
3.2 PriorityQueue常用接口介紹
1. 優(yōu)先級(jí)隊(duì)列的構(gòu)造
有四種PriorityQueue構(gòu)造方式，分別為：
1.傳空參數(shù)：
2：傳數(shù)組的大小的參數(shù)：
3.傳比較器參數(shù)：
4.數(shù)組大小和比較器都傳：
注意：其實(shí)細(xì)心就會(huì)發(fā)現(xiàn)前三種不管傳了什么，都會(huì)調(diào)用第四種方式。
這里我需要解釋一下：
DEFAULT_INITIAL_CAPACITY：基本容量
Comparator<? super E> comparator： 比較器
這是PriorityQueue隊(duì)列在創(chuàng)建堆的分析圖：
默認(rèn)情況下，PriorityQueue隊(duì)列是小堆，如果需要大堆需要用戶提供比較器
這是傳了比較器，通過去重寫compare方法，去創(chuàng)建大堆。
代碼實(shí)現(xiàn)：
class Imp implements Comparator<Integer> {
//通過自己建一個(gè)比較器來將小堆轉(zhuǎn)化為大堆
@Override
public int compare(Integer o1, Integer o2) {
return o2.compareTo(o1);
}
}
public class PrioQueue {
public static void main(String[] args) {
PriorityQueue<Integer> priorityQueue1 = new PriorityQueue<>();
priorityQueue1.offer(1);
priorityQueue1.offer(2);
System.out.println("======");
Imp imp = new Imp();
PriorityQueue<Integer> priorityQueue2= new PriorityQueue<>(imp);
/*priorityQueue2.offer(1);
priorityQueue2.offer(2);
System.out.println("=========");*/
2.PriorityQueue隊(duì)列的一些方法：
4.堆的應(yīng)用
4.1堆排序
如果你需要將數(shù)據(jù)以升序的方式排序，則你必須要一個(gè)大根堆。
1.創(chuàng)建大根堆(前面實(shí)現(xiàn)了)
2.刪除堆頂?shù)脑?br> 3.再從0到end-1向下調(diào)整
4.end–
畫圖演示：
代碼實(shí)現(xiàn)：
public void heapSort() {
int end = usedSize-1;
while(end>0) {
swap(0,end);
siftDown1(0,end-1);
end--;
}
}
//向下調(diào)整的方法
public void siftDown1(int p,int end) {
//得到該結(jié)點(diǎn)的子結(jié)點(diǎn)的下標(biāo)
int c = 2*p + 1;
//臨界條件：子結(jié)點(diǎn)的下標(biāo)<數(shù)組的長(zhǎng)度
while(c < end) {
//找到最大的子結(jié)點(diǎn)
if(c+1<end && elem[c] < elem[c+1]) {
c++;
}
//將該結(jié)點(diǎn)與最大子結(jié)點(diǎn)比較，如小于則交換否則直接break返回
if(elem[p] < elem[c]) {
//交換
swap(p,c);
//將指向該結(jié)點(diǎn)的引用指向該結(jié)點(diǎn)的子結(jié)點(diǎn)，再重新將子結(jié)點(diǎn)的下標(biāo)進(jìn)行變化，檢查該結(jié)點(diǎn)的子樹是否滿足大堆，不滿足則繼續(xù)向下調(diào)整
p = c;
c = 2*p + 1;
} else {
break;
}
}
}
//交換方法
public void swap(int x, int y) {
int tmp = elem[x];
elem[x] = elem[y];
elem[y] = tmp;
}
4.2Top-k問題
TOP-K問題：即求數(shù)據(jù)集合中前K個(gè)最大的元素或者最小的元素，一般情況下數(shù)據(jù)量都比較大。
- 用數(shù)據(jù)集合中前K個(gè)元素來建堆
前k個(gè)最大的元素，則建小堆
前k個(gè)最小的元素，則建大堆 - 用剩余的N-K個(gè)元素依次與堆頂元素來比較，不滿足則替換堆頂元素
將剩余N-K個(gè)元素依次與堆頂元素比完之后，堆中剩余的K個(gè)元素就是所求的前K個(gè)最小或者最大的元素。
代碼實(shí)現(xiàn)：
public int[] smallestK(int[] arr, int k) {
int[] tmp = new int[k];
if (k == 0) {
return tmp;
}
Imp imp = new Imp();
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(imp);
// 建立大堆含k個(gè)元素
for (int i = 0; i < k; i++) {
maxHeap.offer(arr[i]);
}
// 從第k個(gè)元素遍歷
for (int j = k; j < arr.length; j++) {
// 堆頂元素小于數(shù)組下標(biāo)j的大小
if (arr[j] < maxHeap.peek()) {
maxHeap.poll();
maxHeap.offer(arr[j]);
}
}
// 打印這個(gè)大堆中的元素
for (int i = 0; i < tmp.length; i++) {
tmp[i] = maxHeap.poll();
}
return tmp;
}*/
在求找出最小的數(shù)或者找出最大的數(shù)我們應(yīng)該怎么做呢？
有知道的可以在評(píng)論區(qū)分享你的思路或者代碼也行，下篇文章我們來解答這個(gè)問題。文章來源：http://www.zghlxwxcb.cn/news/detail-851526.html
希望大家可以從我的文章中學(xué)到東西，希望大家可以留下點(diǎn)贊收藏加關(guān)注??????????文章來源地址http://www.zghlxwxcb.cn/news/detail-851526.html
到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)】?jī)?yōu)先級(jí)隊(duì)列——堆的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
