一如既往，先上詳細的過程圖。
應用場景
比如求10億個數中的最大的前10個數，時時建構隻有10個元素的小頂堆，如果比堆頂小，則不處理；如果比堆頂大，則替換堆頂，然後依次下沉到适當的位置。
比如求10億個數中的最小的前10個數，時時建構隻有10個元素的大頂堆，如果比堆頂大，則不處理；如果比堆頂小，則替換堆頂，然後依次下沉到适當的位置。
代碼如下，有詳細的注釋
package com.collonn.algorithm.sort;
/**
* <pre>
* 堆排序基本步驟，假設沒有重複的元素
* 空間：為O(1)
* 時間：N*logN
*
* 步驟1：建構大頂堆(或小頂堆)
* 步驟2：将 堆頂 元素 與 未排序 的最後一個葉子，進行交換
* 步驟3：并對半堆進行修正(不考慮已有序的葉子)
* 步驟4：重複步驟2,3
* </pre>
*/
public class HeapSort {
/**
* <pre>
* 建構大頂堆，假設沒有重複的元素
* 1：下标為0的元素，表示元素數量，從下标1開始表示元素值，這樣做的原因僅僅是為了更友善的計算，往下看
* 2：最初，數組中的值，從下标1開始到數組末尾，表示一個完全二叉樹的順序存儲
* 3：那麼可以得出以下位置關系：
* (1)第i個元素的父親是i/2
* (2)第i個元素的左孩子是L=2*i，右孩子是R=2*i+1，即L+1
* 4：假如最後一個元素的下标是i，其雙親下标為j=i/2，我們依次對[1,j]的元素進行堆建構即可
* </pre>
*/
public void initHeap(int[] s) {
// 最後一個葉子的雙親下标
int lastParentIndex = s[0] / 2;
// 對半堆進行修正
for (int i = lastParentIndex; i > 0; i--) {
this.reBuild(i, s, s[0]);
}
}
/**
* <pre>
* 對半堆進行修正，半堆的意思是：除堆頂元素外，其它元素都符合堆定義
* </pre>
*
* @param i 部分元素組成的堆的堆頂
* @param s 元素數組
* @param last 未排序的元素下标
*/
private void reBuild(int i, int[] s, int last) {
System.out.printf("\n-------------------- rebuild --------------------");
System.out.printf("\ni=%d，s[i]=%d, last=%d", i, s[i], last);
// 下标為i的左孩子下标
int L = 2 * i;
// 下标為i的右孩子下标
int R = L + 1;
// 左右孩子中較小的一個
int minLR = -1;
// 下标為i的元素沒有孩子
if (L > last && R > last) {
System.out.printf("\nno children");
return;
}
// 下标為i的元素隻有左孩子
if (L <= last && R > last) {
minLR = L;
}
// 下标為i的元素隻有右孩子
if (L > last && R <= last) {
minLR = R;
}
// 下标為i的元素有兩個孩子
if (L <= last && R <= last) {
minLR = s[L] < s[R] ? R : L;
}
System.out.printf("\nminLr=%d, s[minLR]=%d", minLR, s[minLR]);
// 比較以下三個元素，雙親，雙親的左孩子，雙親的右孩子
if (s[i] > s[minLR]) {
System.out.printf("\n i=%d, s[i]=%d is the max one.", i, s[i]);
return;
} else {
this.swap(i, minLR, s);
// 遞歸進行堆調整
this.reBuild(minLR, s, last);
}
}
// 元素交換
private void swap(int i, int j, int[] s) {
System.out.printf("\nswap, i=%d, s[i]=%d, j=%d, s[j]=%d", i, s[i], j, s[j]);
int t = s[i];
s[i] = s[j];
s[j] = t;
}
/**
* <pre>
* 堆排序
* 1：将 堆頂 元素 與 未排序 的最後一個葉子交換(這個交換後的葉子已是有序的，後面的堆調整，不再考慮這個葉子元素了)
* 2：将堆頂元素按照堆定義，依次進行下沉，直到新堆符合堆定義
* 3：重複1,2
* </pre>
*
* @param s
*/
public void heapSort(int[] s) {
System.out.printf("\n---------------------- heapSort ----------------------");
for (int j = s[0]; j > 0; j--) {
System.out.printf("\n找到最小值:%d", s[1]);
this.swap(1, j, s);
PrintArray(s);
this.reBuild(1, s, j - 1);
PrintArray(s);
}
}
// 列印數組
private static void PrintArray(int[] s) {
System.out.printf("\n-----------------------------------");
System.out.printf("\n下标:");
for (int p = 0; p < s.length; p++) {
System.out.printf("%2d,", p);
}
System.out.print("\n值值:");
for (Integer m : s) {
System.out.printf("%2d,", m);
}
}
public static void main(String[] args) {
// int[] s = new int[] { 99, 88, 5, 99, 7, 9, 3, 8, 10, 90, 56, 83, 39, 22 };
int[] s = new int[] { 7, 5, 2, 8, 3, 1, 6, 9 };
PrintArray(s);
HeapSort heapSort = new HeapSort();
heapSort.initHeap(s);
PrintArray(s);
heapSort.heapSort(s);
PrintArray(s);
}
}
輸出如下：
-----------------------------------
下标: 0, 1, 2, 3, 4, 5, 6, 7,
值值: 7, 5, 2, 8, 3, 1, 6, 9,
-------------------- rebuild --------------------
i=3，s[i]=8, last=7
minLr=7, s[minLR]=9
swap, i=3, s[i]=8, j=7, s[j]=9
-------------------- rebuild --------------------
i=7，s[i]=8, last=7
no children
-------------------- rebuild --------------------
i=2，s[i]=2, last=7
minLr=4, s[minLR]=3
swap, i=2, s[i]=2, j=4, s[j]=3
-------------------- rebuild --------------------
i=4，s[i]=2, last=7
no children
-------------------- rebuild --------------------
i=1，s[i]=5, last=7
minLr=3, s[minLR]=9
swap, i=1, s[i]=5, j=3, s[j]=9
-------------------- rebuild --------------------
i=3，s[i]=5, last=7
minLr=7, s[minLR]=8
swap, i=3, s[i]=5, j=7, s[j]=8
-------------------- rebuild --------------------
i=7，s[i]=5, last=7
no children
-----------------------------------
下标: 0, 1, 2, 3, 4, 5, 6, 7,
值值: 7, 9, 3, 8, 2, 1, 6, 5,
---------------------- heapSort ----------------------
找到最小值:9
swap, i=1, s[i]=9, j=7, s[j]=5
-----------------------------------
下标: 0, 1, 2, 3, 4, 5, 6, 7,
值值: 7, 5, 3, 8, 2, 1, 6, 9,
-------------------- rebuild --------------------
i=1，s[i]=5, last=6
minLr=3, s[minLR]=8
swap, i=1, s[i]=5, j=3, s[j]=8
-------------------- rebuild --------------------
i=3，s[i]=5, last=6
minLr=6, s[minLR]=6
swap, i=3, s[i]=5, j=6, s[j]=6
-------------------- rebuild --------------------
i=6，s[i]=5, last=6
no children
-----------------------------------
下标: 0, 1, 2, 3, 4, 5, 6, 7,
值值: 7, 8, 3, 6, 2, 1, 5, 9,
找到最小值:8
swap, i=1, s[i]=8, j=6, s[j]=5
-----------------------------------
下标: 0, 1, 2, 3, 4, 5, 6, 7,
值值: 7, 5, 3, 6, 2, 1, 8, 9,
-------------------- rebuild --------------------
i=1，s[i]=5, last=5
minLr=3, s[minLR]=6
swap, i=1, s[i]=5, j=3, s[j]=6
-------------------- rebuild --------------------
i=3，s[i]=5, last=5
no children
-----------------------------------
下标: 0, 1, 2, 3, 4, 5, 6, 7,
值值: 7, 6, 3, 5, 2, 1, 8, 9,
找到最小值:6
swap, i=1, s[i]=6, j=5, s[j]=1
-----------------------------------
下标: 0, 1, 2, 3, 4, 5, 6, 7,
值值: 7, 1, 3, 5, 2, 6, 8, 9,
-------------------- rebuild --------------------
i=1，s[i]=1, last=4
minLr=3, s[minLR]=5
swap, i=1, s[i]=1, j=3, s[j]=5
-------------------- rebuild --------------------
i=3，s[i]=1, last=4
no children
-----------------------------------
下标: 0, 1, 2, 3, 4, 5, 6, 7,
值值: 7, 5, 3, 1, 2, 6, 8, 9,
找到最小值:5
swap, i=1, s[i]=5, j=4, s[j]=2
-----------------------------------
下标: 0, 1, 2, 3, 4, 5, 6, 7,
值值: 7, 2, 3, 1, 5, 6, 8, 9,
-------------------- rebuild --------------------
i=1，s[i]=2, last=3
minLr=2, s[minLR]=3
swap, i=1, s[i]=2, j=2, s[j]=3
-------------------- rebuild --------------------
i=2，s[i]=2, last=3
no children
-----------------------------------
下标: 0, 1, 2, 3, 4, 5, 6, 7,
值值: 7, 3, 2, 1, 5, 6, 8, 9,
找到最小值:3
swap, i=1, s[i]=3, j=3, s[j]=1
-----------------------------------
下标: 0, 1, 2, 3, 4, 5, 6, 7,
值值: 7, 1, 2, 3, 5, 6, 8, 9,
-------------------- rebuild --------------------
i=1，s[i]=1, last=2
minLr=2, s[minLR]=2
swap, i=1, s[i]=1, j=2, s[j]=2
-------------------- rebuild --------------------
i=2，s[i]=1, last=2
no children
-----------------------------------
下标: 0, 1, 2, 3, 4, 5, 6, 7,
值值: 7, 2, 1, 3, 5, 6, 8, 9,
找到最小值:2
swap, i=1, s[i]=2, j=2, s[j]=1
-----------------------------------
下标: 0, 1, 2, 3, 4, 5, 6, 7,
值值: 7, 1, 2, 3, 5, 6, 8, 9,
-------------------- rebuild --------------------
i=1，s[i]=1, last=1
no children
-----------------------------------
下标: 0, 1, 2, 3, 4, 5, 6, 7,
值值: 7, 1, 2, 3, 5, 6, 8, 9,
找到最小值:1
swap, i=1, s[i]=1, j=1, s[j]=1
-----------------------------------
下标: 0, 1, 2, 3, 4, 5, 6, 7,
值值: 7, 1, 2, 3, 5, 6, 8, 9,
-------------------- rebuild --------------------
i=1，s[i]=1, last=0
no children
-----------------------------------
下标: 0, 1, 2, 3, 4, 5, 6, 7,
值值: 7, 1, 2, 3, 5, 6, 8, 9,
-----------------------------------
下标: 0, 1, 2, 3, 4, 5, 6, 7,
值值: 7, 1, 2, 3, 5, 6, 8, 9,
原創博文，轉載請注明出處。
![Java小案例——随機數猜測随機數猜測[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)