ヒープソート

• いかなるデータに対しても$O(n\log n)$の計算量
• 平均の計算量ではクイックソートの方が優れている
• 基本的な考え方は「選択ソート」つまり，「ある範囲内での最(大|小)値を見つけて，その位置を確定させる」ことを繰り返すことで整列させる
• 選択ソートでは「ある範囲での最(大|小)値」だけに注目しているので，最(大|小)値を除く他の値同士の大小関係の情報を捨てているが，ヒープソートではその情報をデータ構造の中に残しておくことで計算量を減らす
• ここで求められているのは「複数の値の集合から最大値を効率的に取り出すことができる」ようなデータ構造
• このようなデータ構造は「優先順位つき待ち行列」という
• 優先順位つき待ち行列をどうやって実現するかには複数の選択肢がある
• 例えば優先順位つき待ち行列を平衡木を用いて実現しようとしても全然構わない．その場合，平衡木の右端のノードが最大値になっているのでそこを取り出せばいい．
• が，常に平衡木の右端を取り除くことになるので，最大値を得るたびに木のバランスが崩れ，リバランスの処理が必要になる
• 確かに平衡木を用いて優先度つき待ち行列を実現してもいいが，平衡木ほどリッチなデータ構造でなくても優先度つき待ち行列は実現できる
• それが「部分順序つき木」
• 部分順序つき木では「親はその直の子供より大きい」ような木構造
• 二分探索木の大小関係を縦にした感じ
• 部分順序つき木では木全体の根が常に最大値になっている
• が，しかし，優先度つき待ち行列を部分順序つき木で実現するのはまだリッチで，通常は部分順序つき木を配列を使って表現したものを使う

• 部分順序つき木をよく観察してみると，配列の$i$番目に対して$2i$番目に「$i$の左の子供」$2i+1$番目に「$i$の右の子供」と配置するとルール決めすると，部分順序つき木を配列上に表現できそうだと気がつく

• 配列上に表現した部分順序つき木のことをさしてヒープということがある
• 配列を使って任意のルールを満たす二分木が表現できるかと言われるとそうではない
• 部分順序つき木が配列上に表現できるのは「左右の子供の順番が自由だから」
• 部分順序つき木を配列上で表現すると「全体から数えて$i$番目のノードが親ならば，$2i$番目と$2i+1$番目のノードがその子供になっている」ので，「配列の長さが$n$ならば，全体から数えて$n$番目の子供が存在しているということだから，$n/2$番目のノードが「子供を持っている」ノードの中で最も若い（インデックスが最大）ノードということになる
• ここでやりたいのは，「ランダムな順番になっている配列をヒープに変換して，最大値を取り出す」こと
• ヒープに変換するとはどういうことかといえば，「全ての親について，親子間で部分順序つき木のルール（親≧子）を守らせる」ようにすること
• つまり，$n/2$番目のノード（これが最もインデックスの大きい親）から遡って行きながら，「親≧子」のルールを守っていなければ親子をひっくり返していく == downheap

func HeapSort(target *[]int) []int {
    *target = append([]int{-1}, *target...)
    downheap := func(parent, lastIdx int) {
        parentValue := (*target)[parent]
        for {
            child := 2*parent
            if child > lastIdx { break }
            if child != lastIdx { // `parent` has 2 children
                if  (*target)[child+1] >  (*target)[child] {
                    child += 1
                }
            }
            if  (*target)[child] <= parentValue {
                break
            }
            (*target)[parent] =  (*target)[child]
            parent = child
        }
        (*target)[parent] = parentValue
    }
    n := len(*target)-1
    for i := n/2; 1 <= i; i-- {
        downheap(i, n)
    }
    for i := n; 2 <= i; i-- {
        (*target)[1],  (*target)[i] =  (*target)[i],  (*target)[1]
        downheap(1, i-1)
    }
    return (*target)[1:]
}