二叉堆的定義
二叉堆是完全二叉樹或者是近似完全二叉樹。
二叉堆滿足兩個特性：
- 父節(jié)點的鍵值總是大于或等于（小于或等于）任何一個子節(jié)點的鍵值
-
每個節(jié)點的左子樹和右子樹都是一個二叉堆（都是最大堆或最小堆）
當父節(jié)點的鍵值總是大于或等于任何一個子節(jié)點的鍵值時為最大堆裸诽。當父節(jié)點的鍵值總是小于或等于任何一個子節(jié)點的鍵值時為最小堆。下圖展示一個最小堆：
11B3620D-3236-4882-89D8-0E45CDA8A62D.png
堆的存儲
一般都用數(shù)組來表示堆，i節(jié)點的父節(jié)點下標為（i-1)/2旗笔。它的左右子節(jié)點下標分別為2i+1和2i+2倒脓。如第0個節(jié)點左右子節(jié)點下標分別為1和2.
1A2BD5F2-D816-4846-A220-5C068D3C132C.png
java代碼
public static void heapSort(int[] arr) {
// 將待排序的序列構(gòu)建成一個大頂堆
for (int i = arr.length / 2; i >= 0; i--) {
heapAdjust(arr, i, arr.length);
}
// 逐步將每個最大值的根節(jié)點與末尾元素交換，并且再調(diào)整二叉樹里伯，使其成為大頂堆
for (int i = arr.length - 1; i > 0; i--) {
swap(arr, 0, i); // 將堆頂記錄和當前未經(jīng)排序子序列的最后一個記錄交換
heapAdjust(arr, 0, i); // 交換之后城瞎，需要重新檢查堆是否符合大頂堆，不符合則要調(diào)整
}
}
/**
* 構(gòu)建堆的過程
*
* @param arr 需要排序的數(shù)組
* @param i 需要構(gòu)建堆的根節(jié)點的序號
* @param n 數(shù)組的長度
*/
private static void heapAdjust(int[] arr, int i, int n) {
int currentIndex = i;
while (currentIndex <= n / 2 - 1) {
int leftChildIndex = currentIndex * 2 + 1;
int maxChildIndex = leftChildIndex;
if (leftChildIndex < n - 1) {
if (arr[leftChildIndex] < arr[leftChildIndex + 1]) {
maxChildIndex = leftChildIndex + 1;
}
}
if (arr[currentIndex] < arr[maxChildIndex]) {
int temp = arr[currentIndex];
arr[currentIndex] = arr[maxChildIndex];
arr[maxChildIndex] = temp;
currentIndex = maxChildIndex;
} else {
break;
}
}
}
