ヒープソートってかっこいいよね

/*
ヒープソート(heapsort)
ヒープ構造を用いたソート方法
特徴
1. 「その場」(in place)で実行できる(マージソートやバケットソートは別の配列が必要になる)
2. 最悪でもO(n log n)で実行できる(クイックソートの最悪ケースはO(n^2))
3. かっこいい
4. 安定ではない(たぶん)
5. 平均速度では、クイックソートより定数倍遅いらしい。
*/

/*
完全二分木: どのノードもちょうど2つの子ノードをもち、深さが一定
完全二分木の配列表現
以下のようにインデックスを振る
1 -> 2 -> 4
       -> 5
  -> 3 -> 6
       -> 7
つまり、
xの親:x/2
xの左の子:x*2
xの右の子:x*2+1

ここで、どのノードも親より小さいような完全二分木を「ヒープ」と呼ぶ
ここでは頂点ノードの変更についてのみ記述する
- 頂点ノードに変更があった場合、そこから川下りのように値の入れ替えを行うことで、ヒープ構造を維持できる
- 頂点がどちらの子よりも大きくなるように、どちらかの子と入れ替えを行う
- 入れ替えた子について再帰的に変更を反映する

ここでは、ヒープを配列上に一気に構築して、そこから取りだしていくことで配列をソートする。
*/

#include <cstdio>
#include <iostream>
#include <vector>
#include <utility>
#include <cstdlib>
#include <sys/time.h>

using namespace std;


void heapsort(int n, int *ary)
{
    //ヒープソートでは配列の先頭を1として扱いたいので
    //こうするとary[1]が配列の先頭になる。ary[0]にアクセスしてはいけない
    ary--;
    //木の末端から部分的なヒープを形成していく
    for(int i = n/2; i>=1; i--) {
        int j = i;
        while(true) {
            int nj = j;
            if((j<<1)+0<=n && ary[nj]<ary[(j<<1)+0]) nj=(j<<1)+0;
            if((j<<1)+1<=n && ary[nj]<ary[(j<<1)+1]) nj=(j<<1)+1;
            if(nj==j)break;
            swap(ary[j], ary[nj]);
            j = nj;
        }
    }
    //この時点でヒープ構造が完成する
    while(n>0) {
        //ヒープの末尾と先頭をいれかえることで、ヒープの先頭を取りだす。
        swap(ary[1], ary[n--]);
        //ヒープの修正
        int j = 1;
        while(true) {
            int nj = j;
            if((j<<1)+0<=n && ary[nj]<ary[(j<<1)+0]) nj=(j<<1)+0;
            if((j<<1)+1<=n && ary[nj]<ary[(j<<1)+1]) nj=(j<<1)+1;
            if(nj==j)break;
            swap(ary[j], ary[nj]);
            j = nj;
        }
    }
    return;
}

void sorttest(int asize) {
    int *ary = (int*)malloc(sizeof(int)*asize);
    timeval s,t;
    for(int i = 0; i < asize; i++) {
        ary[i] = rand();
    }
    printf("%d elems:\n",asize);
    gettimeofday(&s, NULL);
    heapsort(asize, ary);
    gettimeofday(&t, NULL);
    for(int i = 0; i < 10; i++) {
        printf("%d, ", ary[i]);
    }
    printf("...\n");
    printf("%fs\n\n", (t.tv_sec-s.tv_sec)+(t.tv_usec-s.tv_usec)/1000000.0);
    free(ary);
}
int main(int argc, char **argv)
{
    srand(1000);
    sorttest(10);
    sorttest(100);
    sorttest(1000);
    sorttest(10000);
    sorttest(100000);
    sorttest(1000000);
    sorttest(3000000);
    sorttest(10000000);
    sorttest(30000000);
    return 0;
}