1. 什么是堆辅辩？
堆其實就是一顆完全二叉樹
堆有大根堆和小根堆炒事，望文生義臀栈，即是根節(jié)點分別是最大和最小節(jié)點。
2.堆的建立
堆的邏輯結(jié)構(gòu)是完全二叉樹挠乳，但是實際可以由數(shù)組來實現(xiàn)权薯，通過下標變換來定位父節(jié)點和左右子節(jié)點。
完全二叉樹中欲侮，下標為i 的節(jié)點
其父節(jié)點是 (i-1)/2
其左孩子是 i2+1
其右孩子是 i2+2
一個數(shù)組必定能夠構(gòu)建一顆完全二叉樹崭闲，只需要按照層序從左往右放置節(jié)點即可肋联。如下圖所示：
由數(shù)組構(gòu)造完全二叉樹
但是這種方式建立的完全二叉樹并非一定是堆威蕉。因為根節(jié)點還一定就是最小最大節(jié)點。
這里以大根堆為例橄仍，講解堆的建立過程韧涨。
/**
* 建堆
* @param arr
*/
public void InitHeap(int[] arr){
if (arr == null || arr.length < 2) {
return;
}
for (int i = 0; i < arr.length; i++) { // 逐個加入,每一個加入都維護成堆
heapInsert(arr, i);
}
}
public static void heapInsert(int[] arr, int index) {
while (arr[index] > arr[(index - 1) / 2]) { // 比父節(jié)點大
swap(arr, index, (index - 1) / 2);
index = (index - 1) / 2; // 節(jié)點往上浮
}
}
// 通過異或交換兩值
public void swap(int[] arr, int i, int j) {
if (arr[i] != arr[j]) {
arr[i] = arr[i] ^ arr[j];
arr[j] = arr[i] ^ arr[j];
arr[i] = arr[i] ^ arr[j];
}
}
3.根彈出后堆的維護 heapify 過程
public static void heapify(int[] arr, int index, int size) {
int left = index * 2 + 1;
while (left < size) {
// 左右節(jié)點需在未排序范圍內(nèi)
int largest = left + 1 < size && arr[left + 1] > arr[left] ? left + 1 : left; // 選擇左右節(jié)點中大者
largest = arr[largest] > arr[index] ? largest : index;
if (largest == index) {
break;
}
swap(arr, largest, index); // 交換父節(jié)點與左右子節(jié)點中大者
index = largest; // 節(jié)點往下沉
left = index * 2 + 1;
}
}
4. 整個堆排序過程
public static void heapSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
for (int i = 0; i < arr.length; i++) {
heapInsert(arr, i);
}
int size = arr.length;
swap(arr, 0, --size);
while (size > 0) {
heapify(arr, 0, size);
swap(arr, 0, --size);
}
}
