(追記)ヒープを作るのに、何だかふつうとはちがう(オリジナルの?)アルゴリズムを採用してしまったようですね。これでもちゃんと動作しますが、ふつうの方法よりも多少効率が悪いようです。最後にふつうの実装も載せます。
ヒープソートですが、まず「(二分木)ヒープ」を作ります。(ここでいうヒープは「ヒープ領域」とは関係ありません。)
ヒープは二分木構造をもっていて、どこを取っても2つの(あるいは最後だけ1つの)子の値よりも、親の値の方が大きいようになっているものです。ヒープはいろいろな使い道があるそうです。まずはヒープを作ってみます。結構むずかしいです。
- 親のインデックスを parent とすると、左側の子のインデックスは parent * 2 + 1 になります。
- 子が存在しない場合は、親のインデックスをひとつ減らして最初から同じことをします。
- 子が存在するばあいは、左の子と右の子で値の大きい方を選び、それを larger とします。
- 親の方が larger 以上ならば、親のインデックスをひとつ減らして最初から同じことをします。
- そうでなければ 親と larger の位置を交換します。そして、その降りてきた親を新しい親として、最初から同じことをします。
終了条件は、親のインデックスが負になった場合です。開始時の親は、配列の最後のその親になります。これのインデックスは、配列の長さを len とすると、(len - 2) / 2 で表されます。
これを C で表現してみましょう。
void build_heap(int ar[], int last) { int child; int parent = (last - 1) / 2; while (parent >= 0) { child = parent * 2 + 1; if (child > last) { parent--; continue; } if (child != last) && ar[child + 1] > ar[child]) child++; if (ar[parent] >= ar[child]) { parent--; continue; } swap(ar, parent, child); parent = child; } }
swap() は値の交換、last は配列の右端のインデックスです。これでヒープを作ることができました。
例えば [4, 1, 6, 2, 9, 7, 3, 8] からヒープを作ると、[9, 8, 7, 4, 1, 6, 3, 2] となります。こういう二分木ですね。
9 -- 8 -- 4 -- 2 -- 1 -- 7 -- 6 -- 3
9 の子が「8, 7」、8 の子が「4, 1」、7 の子が「6, 3」、4 の子が「2」ということです。どこを見ても親の方が大きくなっています。
なお、これは上の方の値が大きくなるので、正確には「最大ヒープ」というものです。上の方ほど小さいヒープは、「最小ヒープ」と呼ばれます。
では、これを使ってソートしてみましょう。
- まずヒープを作ります。
- ヒープの頭(配列の先頭)が最大値なので、これと配列の最後を入れ替えます。
- 配列の最後(最大値)を除いたものを再帰的にソートして、除かれたものを最後に付け加えます。
これがヒープソートです。C で表現するとこんな感じです。
void heap_sort(int ar[], int len) { if (len <= 1) return; build_heap(ar, len - 1); swap(ar, 0, len - 1); heap_sort(ar, len - 1); }
全体のコードとしてはこうなります。
heap_sort.c
#include <stdio.h> void swap(int ar[], int a, int b) { int tmp = ar[a]; ar[a] = ar[b]; ar[b] = tmp; } void build_heap(int ar[], int last) { int child; int parent = (last - 1) / 2; while (parent >= 0) { child = parent * 2 + 1; if (child > last) { parent--; continue; } if (child != last && ar[child + 1] > ar[child]) child++; if (ar[parent] >= ar[child]) { parent--; continue; } swap(ar, parent, child); parent = child; } } void heap_sort(int ar[], int len) { if (len <= 1) return; build_heap(ar, len - 1); swap(ar, 0, len - 1); heap_sort(ar, len - 1); } int main() { int ar[] = {4, 1, 6, 2, 9, 7, 3, 8}; int len = sizeof ar / sizeof(int); heap_sort(ar, len); printf("["); for (int i = 0; i < len; i++) { printf("%d, ", ar[i]); } printf("\b\b]\n"); return 0; }
Go言語版。C の場合とほぼ同じです。
heap_sort.go
package main import "fmt" func build_heap(ar []int) []int { last := len(ar) - 1 parent := (last - 1) / 2 for parent >= 0 { child := parent * 2 + 1 if child > last { parent-- continue } if child != last && ar[child + 1] > ar[child] {child++} if ar[parent] >= ar[child] { parent-- continue } ar[parent], ar[child] = ar[child], ar[parent] parent = child } return ar } func heap_sort(ar []int) []int { len := len(ar) if len <= 1 {return ar} ar = build_heap(ar) ar[0], ar[len - 1] = ar[len - 1], ar[0] return append(heap_sort(ar[:len - 1]), ar[len - 1]) } func main() { ar := heap_sort([]int{4, 1, 6, 2, 9, 7, 3, 8}) fmt.Println(ar) }
ふつうの実装
C言語。
heap_sort1.c
#include <stdio.h> void heapify(int ar[], int parent, int last) { int child, v; v = ar[parent]; while (1) { child = parent * 2 + 1; if (child > last) break; if (child != last && ar[child + 1] > ar[child]) child++; if (v >= ar[child]) break; ar[parent] = ar[child]; parent = child; } ar[parent] = v; } void build_heap(int ar[], int last) { for (int i = (last - 1) / 2; i >= 0; i--) heapify(ar, i, last); } void heap_sort(int ar[], int len) { if (len <= 1) return; build_heap(ar, len - 1); int tmp = ar[0]; ar[0] = ar[len - 1]; ar[len - 1] = tmp; heap_sort(ar, len - 1); } int main() { int ar[] = {4, 1, 6, 2, 9, 7, 3, 8}; int len = sizeof ar / sizeof(int); heap_sort(ar, len); printf("["); for (int i = 0; i < len; i++) { printf("%d, ", ar[i]); } printf("\b\b]\n"); return 0; }
Go言語版。
heap_sort1.go
package main import "fmt" func build_heap(ar []int) []int { heapify := func (parent int) { last := len(ar) - 1 v := ar[parent] for { child := parent * 2 + 1 if child > last {break} if child != last && ar[child + 1] > ar[child] {child++} if v >= ar[child] {break} ar[parent] = ar[child] parent = child } ar[parent] = v } for i:= (len(ar) - 2) / 2; i >= 0; i-- {heapify(i)} return ar } func heap_sort(ar []int) []int { len := len(ar) if len <= 1 {return ar} ar = build_heap(ar) ar[0], ar[len - 1] = ar[len - 1], ar[0] return append(heap_sort(ar[:len - 1]), ar[len - 1]) } func main() { ar := heap_sort([]int{4, 1, 6, 2, 9, 7, 3, 8}) fmt.Println(ar) }
※参考
http://www.th.cs.meiji.ac.jp/assets/researches/2005/omoto/heapsort.html