ヒープは二分木の構造をしている
末端は完全に埋まっていなくてもいいけど左詰めでないといけない
ヒープの条件
ヒープは 構造性 と 順序性 の2つを満たす必要があるじゅう
- 構造性: 完全二分木であること（末端は左詰め）
- 順序性: 親 ≥ 子（maxヒープ）または 親 ≤ 子（minヒープ）
適切なヒープ（maxヒープ）
graph TD A["①:10"] --> B["②:8"] A --> C["③:7"] B --> D["④:5"] B --> E["⑤:6"] C --> F["⑥:3"]
✅ 構造性：完全二分木（左詰め）
✅ 順序性：すべての親 ≥ 子（10≥8, 10≥7, 8≥5, 8≥6, 7≥3）
📝 配列: [_, 10, 8, 7, 5, 6, 3]（インデックス0は未使用）
不適切なヒープ例1：構造性を満たさない
graph TD A["①:10"] --> B["②:8"] A --> C["③:7"] B --> E["⑤:9"] C --> F["⑥:3"]
❌ 構造性：左詰めでない（④が空いて⑤に入っている）
✅ 順序性：親 ≥ 子は満たしている
不適切なヒープ例2：順序性を満たさない
graph TD A["①:10"] --> B["②:12"] A --> C["③:7"] B --> D["④:5"] B --> E["⑤:6"] C --> F["⑥:3"]
✅ 構造性：完全二分木（左詰め）
❌ 順序性：親 < 子になっている（10 < 12）
ヒープソートでのインデックス関係
親 i の左の子: 2i
親 i の右の子: 2i+1
子 i の親: ⌊i/2⌋
ヒープの再構築（pushdown）
ヒープ条件を満たさないノードを、子との入れ替えを繰り返して正しい位置に下ろす操作
void pushdown(recordtype a[], int first, int last){
int r = first, k = 2*r; // r=親, k=左の子（2×親）
while(k <= last){ // 子が存在する限りループ
if (k < last && a[k].key < a[k+1].key){
k++; // 右の子が大きければ、大きい方の子を選択
}
if(a[r].key >= a[k].key){
break; // 親 ≥ 子 → ヒープ条件OK、終了
}
swap(&a[r],&a[k]); // 親 < 子 → 入れ替え
r = k; k = 2*r; // 入れ替えた子を新しい親にして、さらに下へ
}
}ヒープ構築の例（ボトムアップ）
配列 [_, 1, 3, 5, 7, 2, 4, 6, 8, 9, 10] をヒープにする
Step 1: 初期状態（まだヒープではない）
graph TD A["①:1"] --> B["②:3"] A --> C["③:5"] B --> D["④:7"] B --> E["⑤:2"] C --> F["⑥:4"] C --> G["⑦:6"] D --> H["⑧:8"] D --> I["⑨:9"] E --> J["⑩:10"]
Step 2: 最後の親（⑤）からpushdown → ⑤:2 と ⑩:10 を入れ替え
graph TD A["①:1"] --> B["②:3"] A --> C["③:5"] B --> D["④:7"] B --> E["⑤:10"] C --> F["⑥:4"] C --> G["⑦:6"] D --> H["⑧:8"] D --> I["⑨:9"] E --> J["⑩:2"]
Step 3: ④をpushdown → ④:7 と ⑧:8 を入れ替え
graph TD A["①:1"] --> B["②:3"] A --> C["③:5"] B --> D["④:8"] B --> E["⑤:10"] C --> F["⑥:4"] C --> G["⑦:6"] D --> H["⑧:7"] D --> I["⑨:9"] E --> J["⑩:2"]
Step 4: ③をpushdown → ③:5 と ⑦:6 を入れ替え
graph TD A["①:1"] --> B["②:3"] A --> C["③:6"] B --> D["④:8"] B --> E["⑤:10"] C --> F["⑥:4"] C --> G["⑦:5"] D --> H["⑧:7"] D --> I["⑨:9"] E --> J["⑩:2"]
Step 5: ②をpushdown → ②:3 と ⑤:10 を入れ替え
graph TD A["①:1"] --> B["②:10"] A --> C["③:6"] B --> D["④:8"] B --> E["⑤:3"] C --> F["⑥:4"] C --> G["⑦:5"] D --> H["⑧:7"] D --> I["⑨:9"] E --> J["⑩:2"]
Step 6: ①をpushdown → ①:1 と ②:10 を入れ替え → ヒープ完成
graph TD A["①:10"] --> B["②:9"] A --> C["③:6"] B --> D["④:8"] B --> E["⑤:3"] C --> F["⑥:4"] C --> G["⑦:5"] D --> H["⑧:7"] D --> I["⑨:1"] E --> J["⑩:2"]
ヒープソートの実装
void heapsort(recordtype a[], int n){
int i;
// 1. 配列全体をヒープ化（ボトムアップ）
for(i = n/2; i >= 1; i--){
pushdown(a, i, n);
}
// 2. 最大値を取り出して末尾に配置し、残りを再ヒープ化
for(i = n; i >= 2; i--){
swap(&a[1], &a[i]); // ルート（最大値）を末尾と入れ替え
pushdown(a, 1, i-1); // ヒープサイズを縮めて再構築
}
}計算量: O(n log n)
- ヒープ構築: O(n)
- 各取り出し+再構築: O(log n) × n回
ヒープソートは再帰などを必要としない、配列内でヒープを構築できるので膨大なデータを整列するときに便利
分布数え上げソート
累積度数分布を利用する
手順:
- 度数分布表を作成（各値が何個あるか）
- 累積度数分布表に変換（各値までの累積個数）
- 配列の末尾から走査し、累積数が格納場所になる
- 格納したらデクリメントする（同じ値が複数ある場合の対策）
void distribution_counting(recordtype a[], int n){
int i, j, count[m]; // count: 度数分布表（mはデータの範囲）
recordtype b[n+1]; // b: 作業用配列
// 1. 度数分布表を初期化
for(j = 0; j < m; j++){
count[j] = 0;
}
// 2. 度数分布を作成
for(i = 1; i <= n; i++){
count[a[i].key]++;
}
// 3. 累積度数分布に変換
for(j = 1; j < m; j++){
count[j] += count[j-1];
}
// 4. 累積度数に従って並び替え（末尾から走査）
for(i = n; i >= 1; i--){
b[count[a[i].key]] = a[i];
count[a[i].key]--; // 同じ値が複数ある場合に備えてデクリメント
}
// 5. 作業用配列から元の配列にコピー
for(i = 1; i <= n; i++){
a[i] = b[i];
}
}計算量: O(n)（比較不要）
注意点:
- データの範囲が事前に分かっている必要がある
- 作業用配列bとcountが必要（メモリを nhiều 使う）
基数整列法
バケットソートの改良版。整数のみで範囲が大きくてもOK。
基数: 10進数なら10、16進数なら16（桁上がりの基準になる数）
ビット演算で使う関数:
/* xをkビット右へシフトし、その左jビットを取り出す */
int bits(int x, int k, int j){
return (x >> k) & ~(~0 << j);
}基数交換法（上位ビットからソート）:
void radixsort(recordtype a[], int l, int r, int b){
int i, j;
// l < r（要素が2つ以上） && b >= 0（まだ調べるビットがある）
if(l < r && b >= 0){
i = l; j = r;
do{
// 左から0のビットを持つ要素を探す
while(bits(a[i].key, b, 1) == 0 && i < j){
i++;
}
// 右から1のビットを持つ要素を探す
while(bits(a[j].key, b, 1) == 1 && i < j){
j--;
}
if(i != j){ swap(&a[i], &a[j]); }
} while(j != i);
// 末尾が0ならjをインクリメント
if(bits(a[r].key, b, 1) == 0){ j++; }
// 0の部分を再帰的にソート
radixsort(a, l, j-1, b-1);
// 1の部分を再帰的にソート
radixsort(a, j, r, b-1);
}
}呼び出し例: radixsort(a, 1, N, 30) （32bit正整数の場合、符号bit除く）
直接記数法
右から左にビットを調べる（下位ビットから）
sビットまとめてdistribution countingを採用
void directradix(recordtype a[], int n){
int count[m]; // 度数分布表（mはデータの分布数）
int i, j, pass;
recordtype b[n+1]; // 作業用配列
// wはビット長、sは1回で調べるビット数
// w/s回繰り返す（例: 32bit整数を4bitずつなら8回）
for(pass = 0; pass < w/s; pass++){
// 1. 度数分布表を初期化
for(j = 0; j < m; j++){
count[j] = 0;
}
// 2. 度数分布を作成（pass*sビット目からsビットを取り出す）
for(i = 1; i <= n; i++){
count[bits(a[i].key, pass*s, s)]++;
}
// 3. 累積度数分布に変換
for(j = 1; j < m; j++){
count[j] += count[j-1];
}
// 4. 累積度数に従って並び替え（末尾から走査）
for(i = n; i >= 1; i--){
b[count[bits(a[i].key, pass*s, s)]] = a[i];
count[bits(a[i].key, pass*s, s)]--;
}
// 5. 作業用配列から元の配列にコピー
for(i = 1; i <= n; i++){
a[i] = b[i];
}
}
}計算量: O(n)（w/s回のループ × 各ループO(n)）
特徴:
- 右（下位）から左（上位）にビットを調べる
- sビットまとめて比較するので、1ビットずつより効率的
- distribution countingを繰り返すだけ