數據結構 10 基礎數據結構 二叉堆 堆排序演算法詳解
通過上一節的學習，我們了解到
- 二叉堆的本質還是一個完全二叉樹
- 無序數組通過構造、通過下沉構造可以構造為
最小堆 - 通過上浮構造可以構造為
最大堆
來說今天的堆排序演算法之前、首先請和我一起、再次了解一下二叉堆元素的刪除
二叉堆刪除元素
這裡假設我們這裡有這樣的一個完全二叉樹如下：
1、刪除頂部1號元素【暫且放到尾部】、9號元素到達頂部
2、二叉堆進行自我結構的調整、省略調整步驟、9號元素最終到達葉子節點
3、刪除頂部2號元素、8號元素到達頂部。
4、二叉堆盡心自我結構的調整、省略調整步驟
5、繼續刪除頂部3號元素、9號元素到達頂部
我們不難發現：每次通過刪除頂部的元素，通過二叉堆的自我調節、每次刪除的元素呈現出有序
我們可以簡單總結出：
- 將無序的數組構造成二叉堆
- 依次刪除二叉堆頂部元素、藉助二叉堆的自我調節、刪除的元素呈現出有序化
這就是我們今天要整理的 堆排序
程式碼整理
public static void sort(int[] array) {
/**
* 將無序數組調整成二叉堆
*/
buildBinaryHeap(array);
for (int i = array.length - 1; i > 0; i--) {
//刪除對頂、放置到堆尾部、實則交換元素
int temp = array[0];
array[0] = array[i];
array[i] = temp;
//將堆頂部元素進行下沉
sinking(array, 0, i);
}
}
/**
* 構建二叉堆、讓當前元素下沉
*
* @param array 被操作的數組
* @param itemIndex 當前元素下標
* @param length 當前二叉堆長度
*/
public static void sinking(int[] array, int itemIndex, int length) {
//父節點值
int parent = array[itemIndex];
//默認操作的是左孩子
int childIndex = 2 * itemIndex + 1;
while (childIndex < length) {
//存在右邊子元素、並且右邊子元素值小於左邊
if (childIndex + 1 < length && array[childIndex + 1] < array[childIndex]) {
//切換到右邊元素
childIndex++;
}
//小於等於則無需交換
if (parent <= array[childIndex]) break;
//無需交換、只需要將子元素移動到父元素位置即可
array[itemIndex] = array[childIndex];
itemIndex = childIndex;
//改變左右子元素的下標
childIndex = 2 * itemIndex + 1;
}
//最終將父元素移動到指定位置即可。
array[itemIndex] = parent;
}
程式碼只是在上一節的基礎上，我們加了一個sort方法，sort 方法負責首次將無序數組整理成二叉堆、然後從尾部開始循環，將頭部元素和尾部元素進行交換 ,然後將頭部元素元素進行一次下沉 即可。
小結
通過本節的學習，一個數組、也可以玩出如此的花樣、通過構建二叉堆、將頭部元素進行刪除、達到我們排序的目的。
二叉堆作為一個強大的數據結構、還是需要認真學習！
