什麼是堆排序，淺而易懂的對話告訴你！其它頭條網

什麼是堆排序，淺而易懂的對話告訴你！

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

優先級隊列

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

謙子列了幾個要做的事

謙子道出了心中的苦

謙子兩眼發光

克順手畫了一個圖

優先級隊列中每個元素都有優先級優先級最高的最先被處理

優先隊列的實現

謙子非常想知道黑盒裡面是什麼

克非常善於引導學生思考

謙子想了想說

謙子說著說著畫了一個圖

謙子畫了一幅圖解釋道

隨後，謙子又畫出了插入6後的圖

克還是不滿意

堆

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

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

克畫了一個二叉堆實例

注意：二叉堆中兩個孩子之前的大小沒有關係，可能左孩子>=右孩子，也可能右>=左

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

插入操作

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

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

如何調整，謙子心裡想

上浮這個詞形象生動，謙子心裡想

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

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

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

刪除操作

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

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

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

/**
* 對以arr[parentIndex]為父節點的堆進行調整（下沉）
* 在父節點，左右孩子中選出最小的節點，如果最小節點不是父節點則交換
* 繼續下沉，反之不下沉
* @param arr 要調整的數組
* @param parentIndex 父節點的索引
*/
public void sink(int[] arr, int parentIndex) {
 // 堆的大小，第0 個位置無有效值
 int heapSize = arr.length - 1;
 // 從父節點，左孩子和右孩子選出最小節點，得其索引
 int minNodeIndex = minIndex(arr, parentIndex, heapSize);
 // 如果最小的節點的索引不是父節點，則說明最小的節點在左右孩子中，交換並繼續下沉調整
 if (minNodeIndex != parentIndex) {
 swap(arr, minNodeIndex, parentIndex);
 sink(arr, minNodeIndex); // 交換後繼續下沉
 }
}

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

只見謙子又寫了一段代碼

/**
* 求得給定的三個節點的最小節點的索引
* @param parentIndex 父節點的索引
* @param heapSize 堆的大小
* @return 最小節點的索引
*/
private int minIndex(int[] arr, int parentIndex, int heapSize) {
 int minIndex = parentIndex; // 保存最小節點的下標，初始時認為父節點最小
 int leftIndex = leftIndex(parentIndex); // 找到parent的左孩子下標
 // 如果leftIndex沒有越界，比較左孩子和父節點，選擇小的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;
}