Java深入了解數(shù)據(jù)結(jié)構(gòu)之優(yōu)先級隊(duì)列(堆)
一,二叉樹的順序存儲
①存儲方式
使用數(shù)組保存二叉樹結(jié)構(gòu),方式即將二叉樹用層序遍歷方式放入數(shù)組中。 一般只適合表示完全二叉樹,因?yàn)榉峭耆鏄鋾锌臻g的浪費(fèi)。 這種方式的主要用法就是堆的表示。
②下標(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é)點(diǎn)的值都大于其子樹中結(jié)點(diǎn)的值,叫做大堆,或者大根堆,或者最大堆
4. 反之,則是小堆,或者小根堆,或者最小堆
②操作-向下調(diào)整
前提:
左右子樹必須已經(jīng)是一個(gè)堆,才能調(diào)整。
說明:
1. array 代表存儲堆的數(shù)組
2. size 代表數(shù)組中被視為堆數(shù)據(jù)的個(gè)數(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ǎn),則整個(gè)調(diào)整過程結(jié)束
1. 判斷 index 位置有沒有孩子
2. 因?yàn)槎咽峭耆鏄?,沒有左孩子就一定沒有右孩子,所以判斷是否有左孩子
3. 因?yàn)槎训拇鎯Y(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] 的值
Ⅴ然后因?yàn)?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; } } }
③建堆(建大堆為例)
下面我們給出一個(gè)數(shù)組,這個(gè)數(shù)組邏輯上可以看做一顆完全二叉樹,但是還不是一個(gè)堆,現(xiàn)在我們通過算法,把它構(gòu) 建成一個(gè)堆。根節(jié)點(diǎn)左右子樹不是堆,我們怎么調(diào)整呢?這里我們從倒數(shù)的第一個(gè)非葉子節(jié)點(diǎn)的子樹開始調(diào)整,一直 調(diào)整到根節(jié)點(diǎn)的樹,就可以調(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)先級隊(duì)列
①概念
在很多應(yīng)用中,我們通常需要按照優(yōu)先級情況對待處理對象進(jìn)行處理,比如首先處理優(yōu)先級最高的對象,然后處理次 高的對象。最簡單的一個(gè)例子就是,在手機(jī)上玩游戲的時(shí)候,如果有來電,那么系統(tǒng)應(yīng)該優(yōu)先處理打進(jìn)來的電話。 在這種情況下,我們的數(shù)據(jù)結(jié)構(gòu)應(yīng)該提供兩個(gè)最基本的操作,一個(gè)是返回最高優(yōu)先級對象,一個(gè)是添加新的對象。這 種數(shù)據(jù)結(jié)構(gòu)就是優(yōu)先級隊(duì)列(Priority Queue)
②內(nèi)部原理
優(yōu)先級隊(duì)列的實(shí)現(xiàn)方式有很多,但最常見的是使用堆來構(gòu)建。
③入隊(duì)列
過程(以大堆為例):
1. 首先按尾插方式放入數(shù)組
2. 比較其和其雙親的值的大小,如果雙親的值大,則滿足堆的性質(zhì),插入結(jié)束
3. 否則,交換其和雙親位置的值,重新進(jìn)行 2、3 步驟 4. 直到根結(jié)點(diǎn)
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); } }
④出隊(duì)列(優(yōu)先級最高)
為了防止破壞堆的結(jié)構(gòu),刪除時(shí)并不是直接將堆頂元素刪除,而是用數(shù)組的最后一個(gè)元素替換堆頂元素,然后通過向下調(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); }
⑤返回隊(duì)首元素(優(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)先級隊(duì)列(堆)的文章就介紹到這了,更多相關(guān)Java 優(yōu)先級隊(duì)列內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
- Java數(shù)據(jù)結(jié)構(gòu)之優(yōu)先級隊(duì)列(堆)圖文詳解
- 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)-堆實(shí)現(xiàn)優(yōu)先隊(duì)列
- java 數(shù)據(jù)結(jié)構(gòu)之堆排序(HeapSort)詳解及實(shí)例
- Java?超詳細(xì)講解數(shù)據(jù)結(jié)構(gòu)中的堆的應(yīng)用
相關(guān)文章
JavaWeb監(jiān)聽器Listener實(shí)例解析
這篇文章主要為大家詳細(xì)介紹了JavaWeb監(jiān)聽器Listener實(shí)例,針對監(jiān)聽器進(jìn)行進(jìn)行細(xì)致分析,感興趣的小伙伴們可以參考一下2016-08-08Springboot整合多數(shù)據(jù)源配置流程詳細(xì)講解
這篇文章主要介紹了Springboot整合多數(shù)據(jù)源配置流程,文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來一起學(xué)習(xí)吧2023-03-03解決springboot自定義注解AOP在controller上導(dǎo)致controller注入失敗問題
這篇文章主要介紹了解決springboot自定義注解AOP在controller上導(dǎo)致controller注入失敗問題,具有很好的參考價(jià)值,希望對大家有所幫助,如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2023-10-10Java使用EasyExcel進(jìn)行單元格合并的問題詳解
項(xiàng)目中需要導(dǎo)出并合并指定的單元格,下面這篇文章主要給大家介紹了關(guān)于java評論、回復(fù)功能設(shè)計(jì)與實(shí)現(xiàn)的相關(guān)資料,文中通過實(shí)例代碼介紹的非常詳細(xì),需要的朋友可以參考下2022-06-06SpringBoot3?Web編程開發(fā)的工程搭建攔截器及測試工具示例
這篇文章主要介紹了SpringBoot3?Web編程開發(fā)的工程搭建攔截器及測試工具示例詳解,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪2023-08-08