Java深入了解數(shù)據(jù)結(jié)構(gòu)之優(yōu)先級隊列(堆)
一，二叉樹的順序存儲
①存儲方式
使用數(shù)組保存二叉樹結(jié)構(gòu)，方式即將二叉樹用層序遍歷方式放入數(shù)組中。 一般只適合表示完全二叉樹，因為非完全二叉樹會有空間的浪費。 這種方式的主要用法就是堆的表示。
②下標(biāo)關(guān)系
已知雙親(parent)的下標(biāo)，則：
左孩子(left)下標(biāo) = 2 * parent + 1;
右孩子(right)下標(biāo) = 2 * parent + 2;
已知孩子（不區(qū)分左右）(child)下標(biāo)，則：
雙親(parent)下標(biāo) = (child - 1) / 2;
③二叉樹順序遍歷
// 層序遍歷
void levelOrderTraversal(TreeNode root) {
if(root == null) {
return;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
TreeNode top = queue.poll();
System.out.print(top.val+" ");
if(top.left != null) {
queue.offer(top.left);
}
if(top.right!=null) {
queue.offer(top.right);
}
}
System.out.println();
}
二，堆
①概念
1. 堆邏輯上是一棵完全二叉樹
2. 堆物理上是保存在數(shù)組中
3. 滿足任意結(jié)點的值都大于其子樹中結(jié)點的值，叫做大堆，或者大根堆，或者最大堆
4. 反之，則是小堆，或者小根堆，或者最小堆
②操作-向下調(diào)整
前提：
左右子樹必須已經(jīng)是一個堆，才能調(diào)整。
說明：
1. array 代表存儲堆的數(shù)組
2. size 代表數(shù)組中被視為堆數(shù)據(jù)的個數(shù)
3. index 代表要調(diào)整位置的下標(biāo)
4. left 代表 index 左孩子下標(biāo)
5. right 代表 index 右孩子下標(biāo)
6. min 代表 index 的最小值孩子的下標(biāo)?
過程（以小堆為例）：
Ⅰ index 如果已經(jīng)是葉子結(jié)點，則整個調(diào)整過程結(jié)束
1. 判斷 index 位置有沒有孩子
2. 因為堆是完全二叉樹，沒有左孩子就一定沒有右孩子，所以判斷是否有左孩子
3. 因為堆的存儲結(jié)構(gòu)是數(shù)組，所以判斷是否有左孩子即判斷左孩子下標(biāo)是否越界，即 left >= size 越界
Ⅱ 確定 left 或 right，誰是 index 的最小孩子 min
1. 如果右孩子不存在，則 min = left
2. 否則，比較 array[left] 和 array[right] 值得大小，選擇小的為 min
Ⅲ比較 array[index] 的值 和 array[min] 的值，如果 array[index] <= array[min]，則滿足堆的性質(zhì)，調(diào)整結(jié)束
Ⅳ否則，交換 array[index] 和 array[min] 的值
Ⅴ然后因為 min 位置的堆的性質(zhì)可能被破壞，所以把 min 視作 index，向下重復(fù)以上過程
向下調(diào)整是以層序遍歷的二叉樹為例來遍歷
public void adjustDown(int root,int len){
int parent = root;
int child = 2*parent + 1;
while(child < len){
if (child + 1 < len && this.elem[child] < this.elem[child + 1] ){
child++;
}
if(this.elem[child] > this.elem[parent]){
int tmp = this.elem[parent];
this.elem[parent] = this.elem[child];
this.elem[child] = tmp;
parent = child;
child = 2*parent + 1;
}else{
break;
}
}
}
③建堆（建大堆為例）
下面我們給出一個數(shù)組，這個數(shù)組邏輯上可以看做一顆完全二叉樹，但是還不是一個堆，現(xiàn)在我們通過算法，把它構(gòu) 建成一個堆。根節(jié)點左右子樹不是堆，我們怎么調(diào)整呢？這里我們從倒數(shù)的第一個非葉子節(jié)點的子樹開始調(diào)整，一直 調(diào)整到根節(jié)點的樹，就可以調(diào)整成堆。
//建大堆
public void creatHeap(int[] array){
for (int i = 0; i < array.length;i++){
this.elem[i] = array[i];
suedSize++;
}
for (int parent = (array.length - 1 - 1) / 2;parent >= 0;parent--){
adjustDown(parent,this.suedSize);
}
三，堆的應(yīng)用-優(yōu)先級隊列
①概念
在很多應(yīng)用中，我們通常需要按照優(yōu)先級情況對待處理對象進(jìn)行處理，比如首先處理優(yōu)先級最高的對象，然后處理次 高的對象。最簡單的一個例子就是，在手機上玩游戲的時候，如果有來電，那么系統(tǒng)應(yīng)該優(yōu)先處理打進(jìn)來的電話。 在這種情況下，我們的數(shù)據(jù)結(jié)構(gòu)應(yīng)該提供兩個最基本的操作，一個是返回最高優(yōu)先級對象，一個是添加新的對象。這 種數(shù)據(jù)結(jié)構(gòu)就是優(yōu)先級隊列(Priority Queue)
②內(nèi)部原理
優(yōu)先級隊列的實現(xiàn)方式有很多，但最常見的是使用堆來構(gòu)建。
③入隊列
過程（以大堆為例）：
1. 首先按尾插方式放入數(shù)組
2. 比較其和其雙親的值的大小，如果雙親的值大，則滿足堆的性質(zhì)，插入結(jié)束
3. 否則，交換其和雙親位置的值，重新進(jìn)行 2、3 步驟 4. 直到根結(jié)點
public void adjustUp(int child){
int parent = (child - 1) / 2;
while(child>0){
if(this.elem[child] > this.elem[parent]){
int tmp = this.elem[parent];
this.elem[parent] = this.elem[child];
this.elem[child] = tmp;
child = parent;
parent = (child - 1) / 2;
}else {
break;
}
}
}
public void push(int val) {
if (isFull()) {
this.elem = Arrays.copyOf(this.elem, 2 * this.elem.length);
this.elem[this.suedSize] = val;
this.suedSize++;
adjustUp(this.suedSize - 1);
}
}
④出隊列（優(yōu)先級最高）
為了防止破壞堆的結(jié)構(gòu)，刪除時并不是直接將堆頂元素刪除，而是用數(shù)組的最后一個元素替換堆頂元素，然后通過向下調(diào)整方式重新調(diào)整成堆
public boolean isEmpty(){
return this.suedSize == 0;
}
public void pop(){
if(isEmpty()){
return;
}
int tmp = this.elem[0];
this.elem[0] = this.elem[this.suedSize-1];
this.elem[this.suedSize-1] = tmp;
this.suedSize--;
adjustDown(0,this.suedSize);
}
⑤返回隊首元素（優(yōu)先級最高）
public int peek(){
if(isEmpty()){
return -1;
}
return this.elem[0];
}
public boolean isFull(){
return this.suedSize == this.elem.length;
}
四，堆排序
/**
* 一定是先創(chuàng)建大堆
* 調(diào)整每棵樹
* 開始堆排序：
* 先交換 后調(diào)整 直到 0下標(biāo)
*/
public void heapSort(){
int end = this.suedSize-1;
while (end > 0){
int tmp = this.elem[0];
this.elem[0] = this.elem[end];
this.elem[end] = tmp;
adjustDown(0,end);
end--;
}
}
到此這篇關(guān)于Java深入了解數(shù)據(jù)結(jié)構(gòu)之優(yōu)先級隊列(堆)的文章就介紹到這了,更多相關(guān)Java 優(yōu)先級隊列內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
- Java數(shù)據(jù)結(jié)構(gòu)之優(yōu)先級隊列(堆)圖文詳解
- Java 數(shù)據(jù)結(jié)構(gòu)與算法系列精講之二叉堆
- 深入了解Java數(shù)據(jù)結(jié)構(gòu)和算法之堆
- Java數(shù)據(jù)結(jié)構(gòu)中堆的向下和向上調(diào)整解析
- Java 數(shù)據(jù)結(jié)構(gòu)之堆的概念與應(yīng)用
- java數(shù)據(jù)結(jié)構(gòu)-堆實現(xiàn)優(yōu)先隊列
- java 數(shù)據(jù)結(jié)構(gòu)之堆排序（HeapSort）詳解及實例
- Java?超詳細(xì)講解數(shù)據(jù)結(jié)構(gòu)中的堆的應(yīng)用
相關(guān)文章
這篇文章主要介紹了SpringBoot+Vue項目打包部署的相關(guān)資料,包括Vue項目的打包設(shè)置、SpringBoot的配置修改、跨域問題處理、使用Nginx配置反向代理以及最終的項目啟動,教程假定開發(fā)者已具備完整的前后端分離項目和配置好環(huán)境的服務(wù)器,需要的朋友可以參考下2024-10-10
SpringBoot+Mybatis使用Enum枚舉類型總是報錯No enum constant&n
這篇文章主要介紹了SpringBoot+Mybatis使用Enum枚舉類型總是報錯No enum constant XX問題,具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教2023-12-12
Mybatis數(shù)據(jù)批量插入如何實現(xiàn)
這篇文章主要介紹了Mybatis數(shù)據(jù)批量插入如何實現(xiàn),文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友可以參考下2020-07-07
Java for循環(huán)性能優(yōu)化實現(xiàn)解析
Java利用Map實現(xiàn)計算文本中字符個數(shù)
利用Java異常機制實現(xiàn)模擬借書系統(tǒng)
SpringBoot yaml語法與數(shù)據(jù)讀取操作詳解
