實現(xiàn)須知
- 最大堆的性質(zhì)
- 堆是特殊的完全二叉樹
- 所有父節(jié)點的值都比其子節(jié)點的值大
- 堆頂是最大元素
- 堆化一個節(jié)點
- 使該父節(jié)點與其子節(jié)點中值最大的節(jié)點位于該父節(jié)點的位置
- 也即如果有個子節(jié)點是這三個節(jié)點(一父兩子)中最大的，則交換該節(jié)點與父節(jié)點的位置
- 上述步驟(交換兩個節(jié)點的位置)可能導致新的子節(jié)點(原來的父節(jié)點被交換下去變成新的子節(jié)點)作為父節(jié)點時不滿足最大堆的條件，于是再以它為父節(jié)點重復上述步驟，直至到達樹的末端
- 堆化一棵完全二叉樹
- 從最后一個父節(jié)點開始堆化，然后堆化倒數(shù)第二個父節(jié)點，倒數(shù)第三個………直到堆化堆頂節(jié)點
- 本文實現(xiàn)方法是利用最大堆的性質(zhì)"升序"排序，并且基于數(shù)組以及索引的，所以并沒有真正的完全二叉樹類和節(jié)點類
算法思路
- 將要排序的序列看成二叉樹并堆化
- 將堆頂元素與最后一個元素交換，此時最大元素就換到了最后
- 將堆頂節(jié)點堆化
- 重復步驟：
- 交換
要注意最大的元素已經(jīng)被交換到最后，所以每次交換的時候，"最后一個元素"是上一次的前一個 - 堆化堆頂節(jié)點
- 交換
算法實現(xiàn)
具體方法
- 將交換數(shù)組元素的方法
void swap(int[], int, int)進行封裝
/**
* 交換數(shù)組中的兩個數(shù)
*
* @param nums 要交換值的數(shù)組
* @param i 第一個索引
* @param j 第二個索引
* @return void
*/
public static void swap(int[] nums, int i, int j) {
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
- 堆化一個節(jié)點
void nodeHeapify(int[] tree, int index, int N)
參數(shù)N是當前需要堆化的元素個數(shù)- 記錄最大值索引(假定父節(jié)點是最大值)，用于遞歸
- 記錄左右子節(jié)點索引
- 左子節(jié)點索引 = (父節(jié)點索引 * 2) + 1
leftIndex = (index * 2) + 1 - 右子節(jié)點索引 = (父節(jié)點索引 * 2) + 2
rightIndex = (index * 2) + 2
- 左子節(jié)點索引 = (父節(jié)點索引 * 2) + 1
- 分別判斷左右子節(jié)點索引是否越界，再更新最大值索引
- 如果最大值索引不是父節(jié)點索引，則交換父節(jié)點索引與最大值索引的值，然后遞歸堆化
nodeHeapify(tree, maxIndex, N)
/**
* 使某個節(jié)點與他的子節(jié)點符合最大堆的性質(zhì)
*
* @param tree 要進行排序的樹(以數(shù)組形式)
* @param index 要堆化的節(jié)點索引
* @param N 樹的節(jié)點數(shù)
* @return void
*/
public static void nodeHeapify(int[] tree, int index, int N) {
// 找出index索引節(jié)點與它的子節(jié)點中最大的節(jié)點
// 記錄最大值節(jié)點的索引, 用于遞歸
int maxIndex = index;
// 找出左右子節(jié)點的索引
int leftIndex = (index * 2) + 1;
int rightIndex = (index * 2) + 2;
// (索引不越界情況下)如果左子節(jié)點值大于最大值
if (leftIndex < N && tree[leftIndex] > tree[maxIndex]) {
// 更新最大值索引
maxIndex = leftIndex;
}
// (索引不越界情況下)如果右子節(jié)點值大于最大值
if (rightIndex < N && tree[rightIndex] > tree[maxIndex]) {
// 更新最大值索引
maxIndex = rightIndex;
}
// 如果父節(jié)點不是三個節(jié)點中最大的
if (index != maxIndex) {
// 則交換最大值索引與父節(jié)點索引的值(此時三個節(jié)點以滿足最大堆的特性)
swap(tree, index, maxIndex);
// 但是剛才與父節(jié)點交換的節(jié)點, 可能它與它的子節(jié)點因為這次交換而不滿足最大堆特性
// 遞歸, 對剛才被交換的最大值索引的節(jié)點進行堆化
nodeHeapify(tree, maxIndex, N);
}
}
- 堆化一棵完全二叉樹
- 從最后一個父節(jié)點
lastParentIndex = (N - 1 - 1) / 2開始堆化- 最后一個節(jié)點索引
N - 1 - 節(jié)點的父節(jié)點索引
(index - 1) / 2(舍去余數(shù))
- 最后一個節(jié)點索引
- 然后堆化倒數(shù)第二個節(jié)點，依次往上走
for (int i = lastParentIndex; i >= 0; i--)
- 從最后一個父節(jié)點
/**
* 將整個完全二叉樹堆化(每個節(jié)點堆化)
*
* @param tree 要堆化的樹
* @param N 樹的節(jié)點數(shù)
* @return void
*/
public static void treeHeapify(int[] tree, int N) {
// 從最后一個父節(jié)點開始, 往前走, 堆化每個父節(jié)點
int lastParentIndex = (N - 1 - 1) / 2;
for (int i = lastParentIndex; i >= 0; i--) {
nodeHeapify(tree, i, N);
}
}
- 堆排序主體
void heapSort(int[], int)- 首先堆化整棵樹
- 循環(huán)執(zhí)行
for (int i = N - 1; i > 0; i--)交換堆頂和最后一個元素，堆化堆頂元素，i == 0時所有元素已經(jīng)排序好 - 注意：每次最后一個元素是上次一次最后一個元素的前一個，所以每次堆化堆頂元素的時候，把堆的大小當作較少了
1，于是傳進去的參數(shù)N = i(i從N - 1遞減到0)
/**
* 堆排序: 將樹堆化之后, 依次取出堆頂?shù)闹? 重新堆化, 直到取出所有值
*
* @param tree 要排序的數(shù)組
* @param N 樹的節(jié)點數(shù)
* @return int[] result 排序后的數(shù)組
*/
public static void heapSort(int[] tree, int N) {
// 將樹堆化
treeHeapify(tree, N);
// 依次取出堆頂(將最后一個節(jié)點與堆頂?shù)闹祵Q), 堆化堆頂節(jié)點
for (int i = N - 1; i > 0; i--) {
// 堆頂是最大值, 將堆頂與最后一個節(jié)點值交換
// 每循環(huán)一次, 雖然數(shù)組大小不變, 但因為每次都取出堆頂所以堆的"大小" - 1
swap(tree, 0, i);
// 堆化堆頂節(jié)點(注意每次循環(huán)堆的的大小N - 1, 所以參數(shù)N = i)
nodeHeapify(tree, 0, i);
}
}
測試
public static void main(String[] args) {
int[] nums = {1, 4, 7, 5, 2, 6, 3, 8, 9, 1, 4, 7, 8, 5, 2, 3, 1, 4};
System.out.println(Arrays.toString(nums));
heapSort(nums, nums.length);
System.out.println(Arrays.toString(nums));
}
排序前：[ 1, 4, 7, 5, 2, 6, 3, 8, 9, 1, 4, 7, 8, 5, 2, 3, 1, 4 ]
排序后：[ 1, 1, 1, 2, 2, 3, 3, 4, 4, 4, 5, 5, 6, 7, 7, 8, 8, 9 ]
完整代碼
public class HeapSortDemo {
public static void main(String[] args) {
int[] nums = {1, 4, 7, 5, 2, 6, 3, 8, 9, 1, 4, 7, 8, 5, 2, 3, 1, 4};
System.out.println(Arrays.toString(nums));
heapSort(nums, nums.length);
System.out.println(Arrays.toString(nums));
}
/**
* 交換數(shù)組中的兩個數(shù)
*
* @param nums 要交換值的數(shù)組
* @param i 第一個索引
* @param j 第二個索引
* @return void
*/
public static void swap(int[] nums, int i, int j) {
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
/**
* 使某個節(jié)點與他的子節(jié)點符合最大堆的性質(zhì)
*
* @param tree 要進行排序的樹(以數(shù)組形式)
* @param index 要堆化的節(jié)點索引
* @param N 樹的節(jié)點數(shù)
* @return void
*/
public static void nodeHeapify(int[] tree, int index, int N) {
// 找出index索引節(jié)點與它的子節(jié)點中最大的節(jié)點
// 記錄最大值節(jié)點的索引, 用于遞歸
int maxIndex = index;
// 找出左右子節(jié)點的索引
int leftIndex = (index * 2) + 1;
int rightIndex = (index * 2) + 2;
// (索引不越界情況下)如果左子節(jié)點值大于最大值
if (leftIndex < N && tree[leftIndex] > tree[maxIndex]) {
// 更新最大值索引
maxIndex = leftIndex;
}
// (索引不越界情況下)如果右子節(jié)點值大于最大值
if (rightIndex < N && tree[rightIndex] > tree[maxIndex]) {
// 更新最大值索引
maxIndex = rightIndex;
}
// 如果父節(jié)點不是三個節(jié)點中最大的
if (index != maxIndex) {
// 則交換最大值索引與父節(jié)點索引的值(此時三個節(jié)點以滿足最大堆的特性)
swap(tree, index, maxIndex);
// 但是剛才與父節(jié)點交換的節(jié)點, 可能它與它的子節(jié)點因為這次交換而不滿足最大堆特性
// 遞歸, 對剛才被交換的最大值索引的節(jié)點進行堆化
nodeHeapify(tree, maxIndex, N);
}
}
/**
* 將整個完全二叉樹堆化(每個節(jié)點堆化)
*
* @param tree 要堆化的樹
* @param N 樹的節(jié)點數(shù)
* @return void
*/
public static void treeHeapify(int[] tree, int N) {
// 從最后一個父節(jié)點開始, 往前走, 堆化每個父節(jié)點
int lastParentIndex = (N - 1 - 1) / 2;
for (int i = lastParentIndex; i >= 0; i--) {
nodeHeapify(tree, i, N);
}
}
/**
* 堆排序: 將樹堆化之后, 依次取出堆頂?shù)闹? 重新堆化, 直到取出所有值
*
* @param tree 要排序的數(shù)組
* @param N 樹的節(jié)點數(shù)
* @return int[] result 排序后的數(shù)組
*/
public static void heapSort(int[] tree, int N) {
// 將樹堆化
treeHeapify(tree, N);
// 依次取出堆頂(將最后一個節(jié)點與堆頂?shù)闹祵Q), 堆化堆頂節(jié)點
for (int i = N - 1; i > 0; i--) {
// 堆頂是最大值, 將堆頂與最后一個節(jié)點值交換
// 每循環(huán)一次, 雖然數(shù)組大小不變, 但因為每次都取出堆頂所以堆的"大小" - 1
swap(tree, 0, i);
// 堆化堆頂節(jié)點(注意每次循環(huán)堆的的大小N - 1, 所以參數(shù)N = i)
nodeHeapify(tree, 0, i);
}
}
}
