說明
選擇排序法的概念簡單，每次從未排序部份選一最小值，插入已排序部份的後端，其時間主要花費於在整個未排序部份尋找最小值，如果能讓搜尋最小值的方式加 快，選擇排序法的速率也就可以加快，Heap排序法讓搜尋的路徑由樹根至最後一個樹葉，而不是整個未排序部份，因而稱之為改良的選擇排序法。解法
Heap排序法使用Heap Tree（堆積樹），樹是一種資料結構，而堆積樹是一個二元樹，也就是每一個父節點最多只有兩個子節點（關於樹的詳細定義還請見資料結構書籍），堆積樹的 父節點若小於子節點，則稱之為最小堆積（Min Heap），父節點若大於子節點，則稱之為最大堆積（Max Heap），而同一層的子節點則無需理會其大小關係，例如下面就是一個堆積樹：
可以使用一維陣列來儲存堆積樹的所有元素與其順序，為了計算方便，使用的起始索引是1而不是0，索引1是樹根位置，如果左子節點儲存在陣列中的索引為s，則其父節點的索引為s/2，而右子節點為s+1，就如上圖所示，將上圖的堆積樹轉換為一維陣列之後如下所示：
首先必須知道如何建立堆積樹，加至堆積樹的元素會先放置在最後一個樹葉節點位置，然後檢查父節點是否小於子節點（最小堆積），將小的元素不斷與父節點交換，直到滿足堆積樹的條件為止，例如在上圖的堆積加入一個元素12，則堆積樹的調整方式如下所示：
建立好堆積樹之後，樹根一定是所有元素的最小值，您的目的就是：
- 將最小值取出
- 然後調整樹為堆積樹
不斷重複以上的步驟，就可以達到排序的效果，最小值的取出方式是將樹根與最後一個樹葉節點交換，然後切下樹葉節點，重新調整樹為堆積樹，如下所示：
調整完畢後，樹根節點又是最小值了，於是我們可以重覆這個步驟，再取出最小值，並調整樹為堆積樹，如下所示：
如此重覆步驟之後，由於使用一維陣列來儲存堆積樹，每一次將樹葉與樹根交換的動作就是將最小值放至後端的陣列，所以最後陣列就是變為已排序的狀態。
其實堆積在調整的過程中，就是一個選擇的行為，每次將最小值選至樹根，而選擇的路徑並不是所有的元素，而是由樹根至樹葉的路徑，因而可以加快選擇的過程， 所以Heap排序法才會被稱之為改良的選擇排序法。
實作：C Java Python Scala Ruby
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define MAX 10
#define SWAP(x,y) {int t; t = x; x = y; y = t;}
void createHeap(int[]);
void heapSort(int[]);
int main(void) {
srand(time(NULL));
int number[MAX+1] = {-1};
printf("排序前：");
int i;
for(i = 1; i <= MAX; i++) {
number[i] = rand() % 100;
printf("%d ", number[i]);
}
printf("\n建立堆積樹：");
createHeap(number);
for(i = 1; i <= MAX; i++)
printf("%d ", number[i]);
printf("\n");
heapSort(number);
printf("排序後：");
for(i = 1; i <= MAX; i++) {
printf("%d ", number[i]);
}
return 0;
}
void createHeap(int number[]) {
int heap[MAX+1] = {-1};
int i;
for(i = 1; i <= MAX; i++) {
heap[i] = number[i];
int s = i;
int p = i / 2;
while(s >= 2 && heap[p] > heap[s]) {
SWAP(heap[p], heap[s]);
s = p;
p = s / 2;
}
}
int j;
for(j = 1; j <= MAX; j++)
number[j] = heap[j];
}
void heapSort(int number[]) {
int m = MAX;
while(m > 1) {
SWAP(number[1], number[m]);
m--;
int p = 1;
int s = 2 * p;
while(s <= m) {
if(s < m && number[s+1] < number[s])
s++;
if(number[p] <= number[s])
break;
SWAP(number[p], number[s]);
p = s;
s = 2 * p;
}
}
}
public class Sort {
public static void heap(int[] number) {
int[] tmp = new int[number.length + 1];
// 配合說明，使用一個有偏移的暫存陣列
for(int i = 1; i < tmp.length; i++) {
tmp[i] = number[i-1];
}
doHeap(tmp);
int m = number.length;
while(m > 1) {
swap(tmp, 1, m);
m--;
int p = 1;
int s = 2 * p;
while(s <= m) {
if(s < m && tmp[s+1] < tmp[s])
s++;
if(tmp[p] <= tmp[s])
break;
swap(tmp, p, s);
p = s;
s = 2 * p;
}
}
// 這邊將排序好的暫存陣列設定回原陣列
for(int i = 0; i < number.length; i++) {
number[i] = tmp[i+1];
}
}
private static void doHeap(int[] tmp) {
int[] heap = new int[tmp.length];
for(int i = 0; i < heap.length; i++)
heap[i] = -1;
for(int i = 1; i < heap.length; i++) {
heap[i] = tmp[i];
int s = i;
int p = i / 2;
while(s >= 2 && heap[p] > heap[s]) {
swap(heap, p, s);
s = p;
p = s / 2;
}
}
for(int i = 1; i < tmp.length; i++)
tmp[i] = heap[i];
}
private static void swap(int[] number, int i, int j) {
int t = number[i];
number[i] = number[j];
number[j] = t;
}
}
def sort(number):
tmp = [0] * (len(number) + 1)
for i in range(1, len(tmp)):
tmp[i] = number[i - 1]
doHeap(tmp)
m = len(number)
while m > 1:
tmp[1], tmp[m] = tmp[m], tmp[1]
m -= 1
p = 1
s = 2 * p
while s <= m:
if s < m and tmp[s + 1] < tmp[s]:
s += 1
if tmp[p] <= tmp[s]:
break
tmp[p], tmp[s] = tmp[s], tmp[p]
p = s
s = 2 * p
for i in range(len(number)):
number[i] = tmp[i + 1]
def doHeap(tmp):
heap = [-1] * len(tmp)
for i in range(1, len(heap)):
heap[i] = tmp[i]
s = i
p = i // 2
while s >= 2 and heap[p] > heap[s]:
heap[p], heap[s] = heap[s], heap[p]
s = p
p = s // 2
for i in range(1, len(tmp)):
tmp[i] = heap[i]
object Sort {
def heap(number: Array[Int]) {
val tmp = new Array[Int](number.length + 1)
for(i <- 1 until tmp.length)
tmp(i) = number(i - 1)
doHeap(tmp)
var m = number.length
while(m > 1) {
swap(tmp, 1, m)
m -= 1
var p = 1
var s = 2 * p
var isContinue = true
while(s <= m && isContinue) {
if(s < m && tmp(s + 1) < tmp(s))
s += 1
if(tmp(p) <= tmp(s)) {
isContinue = false
} else {
swap(tmp, p, s)
p = s
s = 2 * p
}
}
}
for(i <- 0 until number.length) {
number(i) = tmp(i + 1)
}
}
private def swap(number: Array[Int], i: Int, j: Int) {
val t = number(i)
number(i) = number(j)
number(j) = t
}
private def doHeap(tmp: Array[Int]) {
val heap = new Array[Int](tmp.length)
for(i <- 0 until heap.length)
heap(i) = -1
for(i <- 1 until heap.length) {
heap(i) = tmp(i)
var s = i
var p = i / 2
while(s >= 2 && heap(p) > heap(s)) {
swap(heap, p, s)
s = p
p = s / 2
}
}
for(i <- 1 until tmp.length) {
tmp(i) = heap(i)
}
}
}def sort(number)
tmp = Array.new(number.length + 1, 0)
1.upto(tmp.length - 1) { |i|
tmp[i] = number[i - 1]
}
doHeap(tmp)
m = number.length
while m > 1
tmp[1], tmp[m] = tmp[m], tmp[1]
m -= 1
p = 1
s = 2 * p
while s <= m
if s < m && tmp[s + 1] < tmp[s]
s += 1
end
if tmp[p] <= tmp[s]
break
end
tmp[p], tmp[s] = tmp[s], tmp[p]
p = s
s = 2 * p
end
end
number.length.times { |i|
number[i] = tmp[i + 1]
}
end
def doHeap(tmp)
heap = Array.new(tmp.length, -1)
1.upto(heap.length - 1) { |i|
heap[i] = tmp[i]
s = i
p = i / 2
while s >= 2 && heap[p] > heap[s]
heap[p], heap[s] = heap[s], heap[p]
s = p
p = s / 2
end
}
1.upto(tmp.length - 1) { |i|
tmp[i] = heap[i]
}
end