大小堆及常用堆算法
大小堆
概念上
-
大頂堆:父節(jié)點(diǎn)的值大于等于子節(jié)點(diǎn)的值
-
小頂堆:父節(jié)點(diǎn)的值小于等于子節(jié)點(diǎn)的值
結(jié)構(gòu)上
- 都是完全二叉樹(shù)結(jié)構(gòu)
- 獲取最值都是O(1),插入刪除都是O(log(n))
使用場(chǎng)景
- 大頂堆:用于快速獲取最大值的場(chǎng)景.比如堆排序的升序排序
- 小頂堆:比如優(yōu)先級(jí)隊(duì)列處理優(yōu)先級(jí)高(權(quán)值小)的任務(wù)
常用算法
維護(hù)堆結(jié)構(gòu)涉及兩個(gè)個(gè)主要方法
- heapify() 建堆,用于堆結(jié)構(gòu)的初始化,采用弗洛伊德算法,從最后一個(gè)非葉子節(jié)點(diǎn)開(kāi)始,向前遍歷做down
- down() 下潛節(jié)點(diǎn),新增/刪除節(jié)點(diǎn)后維護(hù)堆結(jié)構(gòu),和左右孩子比較,找到大的做交換,然后遞歸下潛(大頂堆)
public static void heapify(int[] arr) {
for (int i = arr.length / 2 - 1; i >= 0; i--) {//最后一個(gè)非葉子節(jié)點(diǎn)索引為 len*2-1
down(arr, i);
}
}
public static void down(int[] arr, int parent) {
//1.求出左右孩子索引值
int lef = 2 * parent + 1;
int rig = lef + 1;
//2.比較出最大值
int max = parent;
if (lef < arr.length && arr[lef] > arr[max]) {
max = lef;
}
if (rig < arr.length && arr[rig] > arr[max]) {
max = rig;
}
//3.交換,遞歸下潛
if (max!=parent){
swap(arr,parent,max);
down(arr,max);//注意遞歸位置是滿足交換后,此句作為遞歸的終止條件
}
}
public static void swap(int[] arr, int i, int j) {
int t = arr[i];
arr[i] = arr[j];
arr[j] = t;
}
fengdongnan的博客 文章被收錄于專欄
記錄fengdongnan的知識(shí)產(chǎn)出文檔,歡迎大家來(lái)一起交流學(xué)習(xí)
