Java堆&優(yōu)先級(jí)隊(duì)列示例講解(上)
1. 二叉樹的順序存儲(chǔ)
1.1 存儲(chǔ)方式
使用數(shù)組保存二叉樹結(jié)構(gòu),方式即將二叉樹用 層序遍歷 方式放入數(shù)組中。
一般只適合表示完全二叉樹,這種方式的主要用法就是堆的表示。
因?yàn)榉峭耆鏄鋾?huì)有空間的浪費(fèi)(所有非完全二叉樹用鏈?zhǔn)酱鎯?chǔ))。
1.2 下標(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;
2. 堆(heap)
2.1 概念
1. 堆邏輯上是一棵完全二叉樹
2. 堆物理上是保存在數(shù)組中
3. 滿足任意結(jié)點(diǎn)的值都大于其子樹中結(jié)點(diǎn)的值,叫做大堆,或者大根堆,或者最大堆
4. 反之,則是小堆,或者小根堆,或者最小堆
5. 堆的基本作用是,快速找集合中的 最值
2.2 操作-(下沉&上?。┍纠亲畲蠖?/h3>
元素下沉:
/** * 下沉操作 */ public void siftDown(int k){ //還存在子樹 while (leftChild(k) < data.size()){ int j = leftChild(k); //判斷是否存在右子樹且大于左子樹的值 if(j+1 < data.size() && data.get(j+1) > data.get(j)){ j=j+1; } //此時(shí)j為左右子樹最大值 //和當(dāng)前節(jié)點(diǎn)比較大小 if(data.get(j) <= data.get(k)){ break; }else { swap(k,j); k=j; } } }
元素上浮:
/** * 上浮操作 */ // 上浮操作的終止條件: 已經(jīng)走到根節(jié)點(diǎn) || 當(dāng)前節(jié)點(diǎn)值 <= 父節(jié)點(diǎn)值 // 循環(huán)的迭代條件 : 還存在父節(jié)點(diǎn)并且當(dāng)前節(jié)點(diǎn)值 > 父節(jié)點(diǎn)值 private void siftUp(int k) { while (k>0 && data.get(k)>data.get(parent(k))){ swap(k,parent(k)); k=parent(k); } }
其中swap方法是交換操作:
//交換三連 private void swap(int i,int j) { int temp = data.get(j); data.set(j,data.get(i)); data.set(i,temp); }
堆化數(shù)組:
/** * 將任意數(shù)組堆化 * @param arr */ public MaxHeap(int[] arr){ data = new ArrayList<>(arr.length); // 1.先將arr的所有元素復(fù)制到data數(shù)組中 for(int i : arr){ data.add(i); } // 2.從最后一個(gè)非葉子結(jié)點(diǎn)開始進(jìn)行siftDown for (int i = parent(data.size()-1); i >=0 ; i--) { siftDown(i); } }
圖示:
以此數(shù)組為例:
// 調(diào)整前 int[] array = { 27,15,19,18,28,34,65,49,25,37 }; // 調(diào)整后 int[] array = { 15,18,19,25,28,34,65,49,27,37 };
時(shí)間復(fù)雜度分析:
最壞的情況即圖示的情況,從根一路比較到葉子,比較的次數(shù)為完全二叉樹的高度
即時(shí)間復(fù)雜度為 O(log(n))
2.3 建堆-完整代碼(最大堆)
/** * 基于整形最大堆實(shí)現(xiàn) * 時(shí)根節(jié)點(diǎn)從0開始編號(hào),若此時(shí)節(jié)點(diǎn)編號(hào)為k * 左孩子為2k+1 * 右孩子為2k+2 * 父節(jié)點(diǎn)為(k-1)/2 */ import java.util.ArrayList; import java.util.List; import java.util.NoSuchElementException; public class MaxHeap { // 使用JDK的動(dòng)態(tài)數(shù)組(ArrayList)來存儲(chǔ)一個(gè)最大堆 List<Integer> data; // 構(gòu)造方法的this調(diào)用 public MaxHeap(){ this(10); } // 初始化的堆大小 public MaxHeap(int size){ data = new ArrayList<>(size); } /** * 將任意數(shù)組堆化 * @param arr */ public MaxHeap(int[] arr){ data = new ArrayList<>(arr.length); // 1.先將arr的所有元素復(fù)制到data數(shù)組中 for(int i : arr){ data.add(i); } // 2.從最后一個(gè)非葉子結(jié)點(diǎn)開始進(jìn)行siftDown for (int i = parent(data.size()-1); i >=0 ; i--) { siftDown(i); } } /** * 向最大堆中增加值為Value的元素 * @param value */ public void add(int value){ //1.先直接加到堆的末尾 data.add(value); //2.元素上浮操作 siftUp(data.size()-1); } /** * 只找到堆頂元素值 * @return */ public int peekMax (){ if(isEmpty()){ throw new NoSuchElementException("heap is empty!connot peek"); } return data.get(0); } /** * 取出當(dāng)前最大堆的最大值 */ public int extractMax(){ // 取值一定注意判空 if(isEmpty()){ throw new NoSuchElementException("heap is empty!connot extract"); } int max = data.get(0); // 1.將數(shù)組末尾元素頂?shù)蕉秧? int lastValue =data.get(data.size()-1); data.set(0,lastValue); // 2.將數(shù)組末尾的元素刪除 data.remove(data.size()-1); // 3.進(jìn)行元素的下沉操作 siftDown(0); return max; } /** * 下沉操作 */ public void siftDown(int k){ //還存在子樹 while (leftChild(k) < data.size()){ int j = leftChild(k); //判斷是否存在右子樹且大于左子樹的值 if(j+1 < data.size() && data.get(j+1) > data.get(j)){ j=j+1; } //此時(shí)j為左右子樹最大值 //和當(dāng)前節(jié)點(diǎn)比較大小 if(data.get(j) <= data.get(k)){ break; }else { swap(k,j); k=j; } } } /** * 上浮操作 */ // 上浮操作的終止條件: 已經(jīng)走到根節(jié)點(diǎn) || 當(dāng)前節(jié)點(diǎn)值 <= 父節(jié)點(diǎn)值 // 循環(huán)的迭代條件 : 還存在父節(jié)點(diǎn)并且當(dāng)前節(jié)點(diǎn)值 > 父節(jié)點(diǎn)值 private void siftUp(int k) { while (k>0 && data.get(k)>data.get(parent(k))){ swap(k,parent(k)); k=parent(k); } } //交換三連 private void swap(int i,int j) { int temp = data.get(j); data.set(j,data.get(i)); data.set(i,temp); } //判讀堆為空 public boolean isEmpty(){ return data.size() == 0; } //根據(jù)索引找父節(jié)點(diǎn) public int parent(int k){ return (k-1)>>1; } //根據(jù)索引找左孩子 public int leftChild(int k){ return k<<2+1; } //根據(jù)索引找右孩子 public int rightChild(int k){ return k<<2+2; } @Override public String toString() { return data.toString(); } }
ps:隨機(jī)數(shù)操作
int[] data=new int[10000]; //隨機(jī)數(shù) ThreadLocalRandom random = ThreadLocalRandom.current(); for (int i = 0; i < data.length; i++) { data[i] = random.nextInt(); }
3. 優(yōu)先級(jí)隊(duì)列
詳見下節(jié):Java堆&優(yōu)先級(jí)隊(duì)列示例講解(下)
到此這篇關(guān)于Java堆&優(yōu)先級(jí)隊(duì)列示例講解(上)的文章就介紹到這了,更多相關(guān)Java 堆 優(yōu)先級(jí)隊(duì)列內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
基于Springboot使用logback的注意事項(xiàng)
這篇文章主要介紹了Springboot使用logback的注意事項(xiàng),具有很好的參考價(jià)值,希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2021-07-07利用MyBatis進(jìn)行不同條件的like模糊查詢的方法
這篇文章主要介紹了利用MyBatis進(jìn)行不同條件的like模糊查詢,小編覺得挺不錯(cuò)的,現(xiàn)在分享給大家,也給大家做個(gè)參考。一起跟隨小編過來看看吧2018-08-08使用@Validated 和 BindingResult 遇到的坑及解決
這篇文章主要介紹了使用@Validated 和 BindingResult 遇到的坑及解決方案,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2021-10-10Java Object類詳解_動(dòng)力節(jié)點(diǎn)Java學(xué)院整理
Java作為一個(gè)龐大的知識(shí)體系,涉及到的知識(shí)點(diǎn)繁多,本文將從Java中最基本的類java.lang.Object開始談起,對(duì)java object類相關(guān)知識(shí)感興趣的朋友一起學(xué)習(xí)吧2017-04-04SpringMVC 重新定向redirect請(qǐng)求中攜帶數(shù)據(jù)方式
這篇文章主要介紹了SpringMVC 重新定向redirect請(qǐng)求中攜帶數(shù)據(jù)方式,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2021-12-12Java 程序里transient關(guān)鍵字使用方法示例
這篇文章主要為大家介紹了Java 程序里transient關(guān)鍵字使用方法示例,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪2023-11-11在java中使用SPI創(chuàng)建可擴(kuò)展的應(yīng)用程序操作
這篇文章主要介紹了在java中使用SPI創(chuàng)建可擴(kuò)展的應(yīng)用程序操作,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。一起跟隨小編過來看看吧2020-09-09