Java利用完全二叉樹創(chuàng)建大根堆和小根堆
更新時間：2022年08月08日 16:15:09 作者：陳亦康
大根堆是每個結(jié)點的值不大于他的父親結(jié)點的值；小根堆是每個結(jié)點的值不小于他的父親結(jié)點的值。本文將利用完全二叉樹創(chuàng)建大根堆和小根堆，感興趣的可以了解一下
大根堆
大根堆：每個結(jié)點的值不大于他的父親結(jié)點的值
分析如下：
假設對{ 27,15,19,18,28,34,65,49,25,37 }這樣一個集合的數(shù)據(jù)創(chuàng)建成堆；
代碼如下：
//建立大根堆
public class TestHeap{
public int[] array;
public int usedSize;//當前有效數(shù)組長度
public TestHeap(){
this.array = new int[10];
this.usedSize = 0;
}
//初始化數(shù)組
public void InitArray(int[] arrayClone){
array = Arrays.copyOf(arrayClone, arrayClone.length);
usedSize = array.length;
}
//創(chuàng)建大根堆
public void createHeap(){
for(int parent = (usedSize - 1 - 1) / 2; parent >= 0; parent--){
adjustment(parent, usedSize);
}
}
//調(diào)整
public void adjustment(int parent, int len){
//左子樹結(jié)點下標
int child = parent * 2 + 1;
//調(diào)整
while(child < len){
//先判斷有沒有右孩子，如果右，找出最大值
if(child + 1 < len && array[child] < array[child + 1]){
child++;//如果右子樹大，child++就指向他，如果左子樹大，就不用管,直接進行下一步判斷交換
}
//若左右子樹的最大值大于父親結(jié)點則交換
if(array[child] > array[parent]){
swap(array, child, parent);
parent = child;
child = parent * 2 + 1;
} else{
break;
}
}
}
//交換
public void swap(int[] array, int child, int parent){
int tmp = array[child];
array[child] = array[parent];
array[parent] = tmp;
}
}小根堆
小根堆：每個結(jié)點的值不小于他的父親結(jié)點的值
分析與大根堆類似，只是比較出更小的進行替換
代碼如下：
//建立大根堆
public class TestHeap{
public int[] array;
public int usedSize;//當前有效數(shù)組長度
public TestHeap(){
this.array = new int[10];
this.usedSize = 0;
}
//初始化數(shù)組
public void InitArray(int[] arrayClone){
array = Arrays.copyOf(arrayClone, arrayClone.length);
usedSize = array.length;
}
//創(chuàng)建大根堆
public void createHeap(){
for(int parent = (usedSize - 1 - 1) / 2; parent >= 0; parent--){
adjustment(parent, usedSize);
}
}
//調(diào)整
public void adjustment(int parent, int len){
//左子樹結(jié)點下標
int child = parent * 2 + 1;
//調(diào)整
while(child < len){
//先判斷有沒有右孩子，如果右，找出最小值
if(child + 1 < len && array[child] > array[child + 1]){
child++;//如果右子樹小，child++就指向他，如果左子樹小，就不用管,直接進行下一步判斷交換
}
//若左右子樹的最大值小于父親結(jié)點則交換
if(array[child] < array[parent]){
swap(array, child, parent);
parent = child;
child = parent * 2 + 1;
} else{
break;
}
}
}
//交換
public void swap(int[] array, int child, int parent){
int tmp = array[child];
array[child] = array[parent];
array[parent] = tmp;
}
}到此這篇關于Java利用完全二叉樹創(chuàng)建大根堆和小根堆的文章就介紹到這了,更多相關Java大根堆 小根堆內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！
相關文章
SpringCloud Gateway實現(xiàn)限流功能詳解
SpringCloud Gateway 是 Spring Cloud 的一個全新項目，它旨在為微服務架構(gòu)提供一種簡單有效的統(tǒng)一的 API 路由管理方式。這篇文章主要介紹了SpringCloud Gateway實現(xiàn)限流,需要的朋友可以參考下2022-11-11
詳解Spring整合Quartz實現(xiàn)動態(tài)定時任務
本篇文章主要介紹了詳解Spring整合Quartz實現(xiàn)動態(tài)定時任務，具有一定的參考價值，感興趣的小伙伴們可以參考一下。2017-03-03
這篇文章主要介紹了MyBatis Plus之邏輯刪除和分頁插件使用,本文給大家介紹的非常詳細，對大家的學習或工作具有一定的參考借鑒價值，需要的朋友可以參考下2020-12-12
這篇文章主要介紹了java方法重寫和super關鍵字實例詳解的相關資料,需要的朋友可以參考下2017-03-03
這篇文章主要介紹了Java中try catch的使用和如何拋出異常問題,具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教2023-12-12
詳解Springboot集成sentinel實現(xiàn)接口限流入門
這篇文章主要介紹了詳解Springboot集成sentinel實現(xiàn)接口限流入門，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2020-11-11
實踐來源于理論，做開發(fā)前肯定要先了解相關的規(guī)則和原理，看到標題或許你會好奇什么是二三法。本篇文章帶你深入了解,需要的朋友可以參考下2021-10-10
詳解springMVC兩種方式實現(xiàn)多文件上傳及效率比較
本篇文章介紹了springMVC兩種方式實現(xiàn)多文件上傳及效率比較。springMVC實現(xiàn)多文件上傳有兩種，一種是字節(jié)流的方式進行文件上傳，另外一種是使用springMVC包裝好的解析器進行上傳，有興趣的可以了解一下。2016-12-12
微服務架構(gòu)設計RocketMQ基礎及環(huán)境整合
這篇文章主要介紹了微服務架構(gòu)設計入門RocketMQ的基礎及環(huán)境整合實現(xiàn)步驟，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步2021-10-10
java結(jié)合WebSphere MQ實現(xiàn)接收隊列文件功能
WebSphereMQ，也稱MQSeries，以一致的、可靠的和易于管理的方式來連接應用程序，并為跨部門、企業(yè)范圍的集成提供了可靠的基礎。通過為重要的消息和事務提供可靠的、一次且僅一次的傳遞，MQ可以處理復雜的通信協(xié)議，并動態(tài)地將消息傳遞工作負載分配給可用的資源。2015-10-10