1. 最大堆的數(shù)組化表示
假設(shè)有一個(gè)數(shù)組 int[] arr = {8,9,10,11,12,13,14};
用它來(lái)構(gòu)建最大堆
2. 基本思路
- 最大堆或最小堆都是完全二叉樹(shù)，利用這個(gè)性質(zhì)琅翻，先按照數(shù)組順序構(gòu)建最簡(jiǎn)單的完全二叉樹(shù)
- 從最后一個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)（arr.length / 2 - 1）開(kāi)始 逐次調(diào)整位置屁奏，開(kāi)始構(gòu)建最大堆
2.1 若父節(jié)點(diǎn)小于左節(jié)點(diǎn)供填，父節(jié)點(diǎn)與左節(jié)點(diǎn)互換驶忌，繼續(xù)調(diào)整
2.2 若父節(jié)點(diǎn)小于右節(jié)點(diǎn)伟姐，父節(jié)點(diǎn)與右節(jié)點(diǎn)互換（注意是經(jīng)過(guò)2.1）豹芯，繼續(xù)調(diào)整
3. 構(gòu)建示意圖
image.png
4. 源代碼
static int[] arr = {8, 9, 10, 11, 12, 13, 14};
public static void main(String[] args) {
/*
* 調(diào)用建立大頂堆方法：
* index：傳入最后一個(gè)非葉子節(jié)點(diǎn)罚拟，即list.size()/2-1;
* */
for (int i = arr.length / 2 - 1; i >= 0; i--) {
buildHeap(arr, i, arr.length);
}
System.out.println("輸出最大堆：");
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
System.out.println("升序排列結(jié)果：");
heapSort(arr);
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
}
public static void buildHeap(int[] arr, int index, int size) {
int leftchild = 2 * index + 1;
int rightchild = 2 * index + 2;
int temp = index;
if (leftchild < size && arr[index] < arr[leftchild]) {
index = leftchild;
}
if (rightchild < size && arr[index] < arr[rightchild]) {
index = rightchild;
}
if (index != temp) {
swap(arr, temp, index);
// 交換后繼續(xù)向下調(diào)整,以index為父節(jié)點(diǎn)台诗，繼續(xù)向下調(diào)整
buildHeap(arr, index, size);
}
}
/*
* 堆排序：
* 1)將已經(jīng)建立好的大頂堆，每次取出根節(jié)點(diǎn)赐俗，即最大值拉队。
* 2)將最后一個(gè)節(jié)點(diǎn)的值賦給根節(jié)點(diǎn)，重新構(gòu)建大頂堆阻逮。
* 3)刪除最后節(jié)點(diǎn)的數(shù)據(jù)
* */
public static void heapSort(int[] arr) {
for (int i = arr.length - 1; i >= 0; i--) {
swap(arr, i, 0);
// 從根節(jié)點(diǎn)向下調(diào)整粱快，每次取出一個(gè)數(shù)值，集合長(zhǎng)度逐漸減小
buildHeap(arr, 0, i);
}
}
public static void swap(int[] a, int i, int j) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
5 堆排序
基本思路
1)將已經(jīng)建立好的大頂堆叔扼，每次取根節(jié)點(diǎn)事哭，即最大值，并與最后的節(jié)點(diǎn)交換瓜富。
2)重新構(gòu)建大頂堆鳍咱，注意索引是從int i = arr.length - 1 開(kāi)始的，重建大頂堆時(shí)与柑，實(shí)際上相當(dāng)于刪除了最后一個(gè)元素谤辜，即刪除了剛剛完成第一步交換的最大值蓄坏。對(duì)于數(shù)組來(lái)說(shuō)，剛好是將最大值丑念，固定在最后的索引上涡戳。
