ヒープソート(C言語、Go言語)

(追記)ヒープを作るのに、何だかふつうとはちがう(オリジナルの?)アルゴリズムを採用してしまったようですね。これでもちゃんと動作しますが、ふつうの方法よりも多少効率が悪いようです。最後にふつうの実装も載せます。



 
ヒープソートですが、まず「(二分木)ヒープ」を作ります。(ここでいうヒープは「ヒープ領域」とは関係ありません。)

ヒープは二分木構造をもっていて、どこを取っても2つの(あるいは最後だけ1つの)子の値よりも、親の値の方が大きいようになっているものです。ヒープはいろいろな使い道があるそうです。まずはヒープを作ってみます。結構むずかしいです。

  1. 親のインデックスを parent とすると、左側の子のインデックスは parent * 2 + 1 になります。
  2. 子が存在しない場合は、親のインデックスをひとつ減らして最初から同じことをします。
  3. 子が存在するばあいは、左の子と右の子で値の大きい方を選び、それを 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」ということです。どこを見ても親の方が大きくなっています。

なお、これは上の方の値が大きくなるので、正確には「最大ヒープ」というものです。上の方ほど小さいヒープは、「最小ヒープ」と呼ばれます。
 

では、これを使ってソートしてみましょう。

  1. まずヒープを作ります。
  2. ヒープの頭(配列の先頭)が最大値なので、これと配列の最後を入れ替えます。
  3. 配列の最後(最大値)を除いたものを再帰的にソートして、除かれたものを最後に付け加えます。

これがヒープソートです。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