閱讀原文

理解堆排，首先要理解二叉堆侈百。理解了二叉堆的“下沉”操作瓮下，基本上就可以理解堆排了。今天我們來看一看什么是堆钝域，以及堆的一般操作

優(yōu)先級隊列

近日讽坏，謙子遇到了煩心事，于是找老師去訴苦了

1.png

謙子列了幾個要做的事

2.png

3.png

謙子兩眼發(fā)光

4.png

5.png

優(yōu)先級隊列中每個元素都有優(yōu)先級優(yōu)先級最高的最先被處理

優(yōu)先隊列的實現(xiàn)

6.png

謙子非常想知道黑盒里面是什么

7.png

克非常善于引導學生思考

8.png

10.png

11.png

謙子畫了一幅圖解釋道

12.png

13.png

14.png

堆

15.png

這里我們只討論二叉堆震缭，把二叉堆稱為堆
堆也有d-堆，左式堆等等

16.png

克看謙子不是很明白战虏，順手畫了個圖

17.png

克畫了一個二叉堆實例

18.png

注意：二叉堆中兩個孩子之前的大小沒有關(guān)系拣宰，可能左孩子>=右孩子，也可能右>=左

19.png

克隨手畫了一個小根堆和一個大根堆

20.png

21.png

22.png

插入操作

23.png

每個父節(jié)點的值小于等于其左右孩子的值被稱為堆的有序性
另一種情況是大于等于也稱之為堆的有序性

克隨手畫了一個插入操作破壞堆有序性的圖

24.png

如何調(diào)整烦感，謙子心里想

25.png

26.png

說完，克飛速地寫出了上浮的代碼

/**
* 如果待插入的元素小于其父手趣，則交換子和父晌该，并繼續(xù)上浮肥荔，直到大于等于其父
* @param arr 儲存堆的數(shù)組，元素從下標1開始有效朝群，0位置不存在有效值
* @param inserted 被插入節(jié)點的索引
*/
public void swim(int[] arr, int inserted) {
    int parent = inserted/2;
    if (arr[inserted] < arr[parent]) {
        swap(arr, inserted, parent);
        swim(arr, parent);
    }
}

謙子暗自驚嘆老師的代碼功力

刪除操作

29.png

謙子聽完此話緊張的手心出汗燕耿，但還是硬著頭皮想了想，突然靈光一現(xiàn)

30.png

隨后謙子畫出了交換后的圖

31.png

32.png

33.png

34.png

35.png

謙子剛松了口氣姜胖，誰知還要寫代碼誉帅，只見謙子想了想，寫寫擦擦好幾遍最終寫下了如下代碼

/**
* 對以arr[parentIndex]為父節(jié)點的堆進行調(diào)整（下沉）
* 在父節(jié)點右莱，左右孩子中選出最小的節(jié)點蚜锨，如果最小節(jié)點不是父節(jié)點則交換
* 繼續(xù)下沉，反之不下沉
* @param arr 要調(diào)整的數(shù)組
* @param parentIndex 父節(jié)點的索引
*/
public void sink(int[] arr, int parentIndex) {
    // 堆的大小慢蜓，第0 個位置無有效值
    int heapSize = arr.length - 1;
    // 從父節(jié)點亚再，左孩子和右孩子選出最小節(jié)點，得其索引
    int minNodeIndex = minIndex(arr, parentIndex, heapSize);
    // 如果最小的節(jié)點的索引不是父節(jié)點晨抡，則說明最小的節(jié)點在左右孩子中氛悬，交換并繼續(xù)下沉調(diào)整
    if (minNodeIndex != parentIndex) {
        swap(arr, minNodeIndex, parentIndex);
        sink(arr, minNodeIndex);   // 交換后繼續(xù)下沉
    }
}

36.png

慧子解釋道，并畫了一個圖

37.png

只見謙子又寫了一段代碼

/**
* 求得給定的三個節(jié)點的最小節(jié)點的索引
* @param parentIndex 父節(jié)點的索引
* @param heapSize 堆的大小
* @return 最小節(jié)點的索引
*/
private int minIndex(int[] arr, int parentIndex, int heapSize) {
    int minIndex = parentIndex; // 保存最小節(jié)點的下標凄诞，初始時認為父節(jié)點最小
    int leftIndex = leftIndex(parentIndex);  // 找到parent的左孩子下標
    // 如果leftIndex沒有越界圆雁，比較左孩子和父節(jié)點，選擇小的Node的下標賦給minIndex
    if (leftIndex <= heapSize) {
        minIndex = arr[leftIndex] < arr[parentIndex] ? leftIndex : parentIndex;
    }
    int rightIndex = rightIndex(parentIndex);
    if (rightIndex < heapSize) {
        minIndex = arr[rightIndex] < arr[minIndex] ? rightIndex : minIndex;
    }
    return minIndex;
}

leftIndex = 2parentIndex;
rightIndex = 2parentIndex+1;

40.png

看來以后得好好學數(shù)據(jù)結(jié)構(gòu)與算法了帆谍，不然連時間都管理不好伪朽，謙子心想
摘錄自：碼分享