堆排序
堆排序(Heapsort) 是指利用堆這種數(shù)據(jù)結(jié)構(gòu)所設(shè)計(jì)的一種排序算法. 堆是一個近似完全二叉樹的結(jié)構(gòu), 并同時滿足堆的性質(zhì): 即子節(jié)點(diǎn)的鍵值或索引總是大/小于它的父節(jié)點(diǎn)
若堆是什么樣的結(jié)構(gòu)不清楚的, 可以點(diǎn)這里
堆節(jié)點(diǎn)的訪問
通常堆是通過數(shù)組來實(shí)現(xiàn)的, i是堆中的一個節(jié)點(diǎn)的下標(biāo), 則:
父節(jié)點(diǎn)下標(biāo): (i -1) >>> 1;
左子節(jié)點(diǎn)的下標(biāo): 2*i + 1;
右子節(jié)點(diǎn)的下標(biāo): 2*1 + 2;
堆排序的策略
- 從最后一個 parent節(jié)點(diǎn)開始, 塑造最大堆(就是將parent, left, right 中的最大值放置到 parent位置), 一直到堆頂, 經(jīng)過這一步, 整個堆中的最大值就位于index=0的位置
- 將第一步中的最大值(index=0)與數(shù)組的末尾節(jié)點(diǎn)兌換(注意這時 index=2 和 index=3都是下面子堆的最大值), 再在剩余部分構(gòu)建最大值, 然后再重復(fù)將最大值與剩余數(shù)組中最后節(jié)點(diǎn)更換值, 再次構(gòu)建最大堆, 直到最后一個元素.
廢話不說了, 直接上代碼:
import java.util.Arrays;
/**
* Created by xjk on 1/12/17.
*/
public class HeapSort {
private static int[] sort = new int[]{1, 0, 10, 20, 3, 5, 6, 4, 9, 8, 12, 17, 34, 11};
public static void main(String[] args) {
buildMaxHeapify(sort);
heapSort(sort);
System.out.println(Arrays.toString(sort));
}
/**
* 創(chuàng)建最大樹
* @param data
*/
private static void buildMaxHeapify(int[] data){
// 獲取數(shù)組的最后一個父節(jié)點(diǎn)的index
int startIndex = getParentIndex(data.length - 1);
// 從最后一個父節(jié)點(diǎn)開始排序
// 每次調(diào)用 maxHeapify 其實(shí)是將一顆二叉樹中最大的值放到parent位置, 而這里是從底層往上
// 從而最終效果是, 整個數(shù)組中的每棵樹的最大值都在parent位置
for(int i = startIndex; i >= 0; i--){
maxHeapify(data, data.length, i);
}
}
private static void heapSort(int[] data){
// 1. 將最大樹的頭節(jié)點(diǎn)(即整棵樹的最大值)與末尾節(jié)點(diǎn)交換
// 2. 排除最大值, 數(shù)組的剩余部分進(jìn)行最大值排序
// 3. 重復(fù) 1, 2 步驟, 直達(dá)最頂?shù)哪莻€節(jié)點(diǎn)
for(int i = data.length - 1; i > 0; i--){
int temp = data[0];
data[0] = data[i];
data[i] = temp;
maxHeapify(data, i, 0);
}
}
/**
* 創(chuàng)建最大堆
* @param data
* @param heapSize 需要創(chuàng)建最大堆的大小, 一般在sort時候會用到
* @param index 當(dāng)前需要創(chuàng)建最大堆的位置
*/
private static void maxHeapify(int[] data, int heapSize, int index){
// 當(dāng)前點(diǎn)與左右子節(jié)點(diǎn)的比較
int left = getLeftChildIndex(index);
int right = getRightChildIndex(index);
int largest = index;
if(left < heapSize && data[index] < data[left]){
largest = left;
}
if(right < heapSize && data[largest] < data[right]){
largest = right;
}
// 獲取子節(jié)點(diǎn)中的最大值后可能需要交換, 交換后最大的值就在父節(jié)點(diǎn)
if(largest != index){
int temp = data[index];
data[index] = data[largest];
data[largest] = temp;
maxHeapify(data, heapSize, largest);
}
}
/**
* 獲取父節(jié)點(diǎn)
* @param current
* @return
*/
private static int getParentIndex(int current){
return (current - 1) >>> 1;
}
/**
* 獲取左子節(jié)點(diǎn)的
* @param current
* @return
*/
private static int getLeftChildIndex(int current){
return (current << 1) + 1;
}
/**
* 獲取右子節(jié)點(diǎn)的坐標(biāo)
* @param current
* @return
*/
private static int getRightChildIndex(int current){
return (current << 1) + 2;
}
}
總結(jié)
整堆排序過程其實(shí)就三步:
- 構(gòu)建最大堆(buildMaxHeapify)
- 將頭節(jié)點(diǎn)與為節(jié)點(diǎn)更換, 更換后將除尾節(jié)點(diǎn)外的數(shù)組看作一個堆, 對這個堆進(jìn)行最大值排序(heapSort)
- 重復(fù)第二步, 直達(dá)最后一個節(jié)點(diǎn) (heapSort)
參考資料:
HeapSort
vickyqi 堆排序
