ヒープソート
概要
ヒープソートとは，グループに対する要素の追加と最大値の取り出しが高速に行えるヒープというデータ構造を使って行うソートです． 列の全ての要素からなる最大値の取り出しに対応したヒープを構築した後，ヒープの根 (つまりヒープ内での最大値) を取り出して列の末尾に追加していきます．
ヒープはちょうど含まれる要素数の大きさの分しかメモリを使わないため inplace で実装することができます． 僕は配列の先頭から 0-origin で 1 番目の要素を根として前から $i$ 番目の子を $2i$ と $2i+1$ に置く実装が好きなので，下の実装ではまず配列の最小値を列の先頭に持ってきたあと残りの部分でヒープソートを行っています．
計算量
$O(n \log n)$
実装
template <typename T>
void heapsort(T *l, T *r) {
if (r - l < 2) return;
for (T *i = l; i != r; i++)
if (*i < *l) swap(*i, *l);
for (T *i = l + 1; i != r; i++) {
int c = i - l;
while (c != 1) {
int p = c / 2;
if (l[p] >= l[c]) break;
std::swap(l[p], l[c]);
std::swap(c, p);
}
}
for (T *i = r - 1; i != l + 1; i--) {
int sz = i - l - 1, p = 1;
swap(l[1], *i);
while (p * 2 <= sz) {
int a = p * 2;
int b = p * 2 + 1;
if (b <= sz && l[b] > l[a]) a = b;
if (l[a] <= l[p]) break;
std::swap(l[p], l[a]);
std::swap(p, a);
}
}
}