LoginSignup
1
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

@TETSURO1999

ヒープソートを作って学ぶ

Last updated at Posted at 2025-06-29

はじめに

これまで .NET (Framework) の Array.Sort の謎について調査を行ってきた。

筆者の調査によると（というかマイクロソフトの公式サイトにしっかり記載されているが）Array.Sort はクイックソートで始まり，再帰関数の呼び出しが深くなるとヒープソートに切り替わるようになっている。このような仕組みをイントロソートと呼ぶらしい。

このヒープソートについて今までは存在を知っていたに過ぎない。というのもヒープ領域のヒープと紛らわしい命名をしやがって・・・という嫌悪感が先行して，あまり真剣に学習する意欲が湧かなかったからだ。だが，今回ヒープソートを作ってみてようやく理解することができた。先に結論を述べると以下のようになる。

  • 基本概念を理解するのに少し時間がかかるかもしれない。※個人の感想です
  • コードはとてもシンプルである。マージソートよりも短い。
  • 実行時間はマージソートの２倍程度要する。要するに遅い。計算量は $O(n \log n)$ だが，係数が大きい。

ヒープ構造とは？

代表的な二分木構造を例にとる。

１）一次元配列上に仮想的に木構造を置いたものである。一次元配列上の親要素の位置を $i \ge 0$ とおくと，二つの子要素の位置は $2i + 1$，$2i + 2$ と定まる。逆に子要素の位置を $i$ とおくと親要素の位置は $(i - 1) / 2$ と求まる。このように親子のリンクを辿るのに配列のインデクスの計算だけで済み，C言語でいうポインタ●●●●のような情報を必要としない。

２）親要素の値は二つの子要素の値と同じか，より大きい。この結果，最上層（図１のＡ）が最大値になる。なお，二つの子要素同士の大きさは問わない。

３）最下層の要素（図１のＨ～Ｎ）は左から順番に埋まる。

ヒープソートの基本原理

(1) 初期状態

すでにヒープ構造が作成されているものとする。すなわち最上層のＡが最大値となっている。

(2) 最上層の交換

最上層のＡと最下層の最右端のＮを交換し，最右端の要素をヒープ構造から外す。最大値Ａを一次元配列の末尾に置くことになる。

(3) ヒープ構造の作り直し

最上層を入れ替えたことにより，ヒープ構造（親要素が子要素と等しいか，より大きいこと）の条件が崩れているので，一次元配列の末尾のデータを除いてヒープ構造を作り直す。最下層からＮを最上層へ引き上げたが，もともとＮは最下層にあったことから小さな値であり，ヒープ構造の作り直しにより再び下層へ沈んでいくことになる。

(4) 最上層の交換～二度目

最上層のＢと最下層の最右端のＭを交換し，最下層の最右端の要素をヒープ構造から外す。Ａに続いて大きな値であるＢを一次元配列の末尾から二番目に置くことになる。

このような処理を繰り返すとヒープ構造の要素が無くなる一方，一次元配列には末尾から順に大きな値が格納されることになり，先頭から見れば数値が昇順にソートされる。

なぜ最上層と最下層の最右端を交換するのだろうか？
もともと最下層のデータは小さな値であるから，最上層に引き上げてもヒープ構造の作り直しによりどうせ下層に落ちてくるだろう。まるで新入社員をいきなり社長に抜擢するようなもので一見無駄に見える。最上層に置くのなら上から二番目の層から選んだほうが良いのでは？と思われるかもしれない。副社長を社長に引き上げるイメージだ。ただし，その場合は空いた副社長のポストをその部下から引き上げることになり，さらに空いたポストをその部下から引き上げていくことになるが，

３）最下層の要素は左から順番に埋まる。

という条件を守るのが難しくなる。ということで最下層の最右端と入れ替えているものと思われる。

ヒープ構造の作り方

挿入ソートとの類似性

いきなりヒープ構造の作り方を説明する前に，まず挿入ソートについて説明しようと思う。というのもヒープ構造の作り方と類似性があり，挿入ソートを知っていればヒープソートの理解が進むと思うからだ。なお，挿入ソートの実装方法についてはいくつかバリエーションがあるが，ヒープソートと対比し易い形のものを選んだ。

長さ len の整数配列 a[] があり，parent の次の要素から末尾までは既に（昇順）ソート済みの状態とする。ここで parent の位置の要素を加えてソートし直すことを考える。

parent の位置の要素をソート済みの領域の要素と順に比較していき，parent の値より小さな要素■が左側，parent の値以上の要素■が右側になるような位置に parent の要素を挿入する。

こうして配列の末尾からソート済みの領域を一つずつ増やしていけばいい。

上記のアルゴリズムをコードにすると以下のようになる。通常，挿入ソートでは要素の親子関係を意識することは無いと思うが，親 parent の次の要素（右隣の要素）が子 child であると考えると次に示すヒープソートのコードと極めて似た形になる。

挿入ソート
typedef int     (*COMPARE)(int, int);
static  void    insert(int *a, int len, int parent, COMPARE compare) {
    int d = a[parent];
    int child;
    while((child = parent + 1) < len) {
        if(compare(d, a[child]) <= 0) break;
        a[parent] = a[child];
        parent = child;
    }
    a[parent] = d;
}
void    isort(int *a, int len, COMPARE compare) {
    if(len < 2) return;
    for(int i = len - 2; i >= 0; i--)
        insert(a, len, i, compare);
}

このような挿入ソートは計算量 $O(n^2)$ となることから本格的なソート手法としては全面的には採用されないが，小さな配列だと速いので部分的に用いられることもある。特にメモリの移動を要することからあまりパフォーマンスは上がらないように思われるが，シーケンシャルアクセスのため実際はキャッシュが効いて意外と速いのだろう。

ヒープ構造の作り方

ヒープ構造作成済みの二つの山（ヒープ）があり，それらの親の位置に新たな要素を加えてヒープ構造を作り直すことを考える。※ヒープ構造自体は降順で並べるものとする。

子要素は（最大）二つあるので，そのうち大きなほうと比較して親要素のほうが大きければ終了し，親要素のほうが小さければさらに子要素を探っていく。コードにすると下記のようになる。

ヒープ構造の作り方
static  void    heap(int *a, int len, int parent, COMPARE compare) {
    int d = a[parent];
    int child;
    while((child = 2 * parent + 1) < len) {
        if(child + 1 < len && compare(a[child], a[child + 1]) < 0)
            child++;
        if(compare(d, a[child]) >= 0) break;
        a[parent] = a[child];
        parent = child;
    }
    a[parent] = d;
}

上記の関数 heap() と関数 insert() を見比べると非常に構造がよく似ていることが分かる。

実装コード

実行コードを以下に示す。とても短いので全容を示そう。

ヒープソート
typedef int     (*COMPARE)(int, int);
 static  void    swap(int *p, int *q) {
    int temp = *p;
    *p = *q;
    *q = temp;
}
static  void    heap(int *a, int len, int parent, COMPARE compare) {
    int d = a[parent];
    int child;
    while((child = 2 * parent + 1) < len) {
        if(child + 1 < len && compare(a[child], a[child + 1]) < 0)
            child++;
        if(compare(d, a[child]) >= 0) break;
        a[parent] = a[child];
        parent = child;
    }
    a[parent] = d;
}
void    hsort(int *a, int len, COMPARE compare) {
    for(int i = len / 2 - 1; i >= 0; i--)
        heap(a, len, i, compare);
    for(int i = len - 1; i > 0; i--) {
        swap(&a[0], &a[i]);
        heap(a, i, 0, compare);
    }
}

ソートを行うためにヒープ構造を作る関数 heap() を二回に分けて呼び出している。まず，一回目の呼び出しによって配列 a[] 全体をヒープ構造に変換する。親要素の位置 $i$，配列の要素数 $n$ とおくと，少なくとも子要素が一つ存在する条件は $2i + 1 \le n - 1$ であるから，親要素の位置の範囲は $i \le n / 2 - 1$ となる。すなわち下記のループは少なくとも子要素が一つ存在する親要素を対象としたものだ。

一回目の呼び出し
    for(int i = len / 2 - 1; i >= 0; i--)
        heap(a, len, i, compare);

二回目の呼び出しはヒープ構造の最上層（つまり最大値）を配列の末尾と交換することで，昇順ソートを行っていく。

二回目の呼び出し
    for(int i = len - 1; i > 0; i--) {
        swap(&a[0], &a[i]);
        heap(a, i, 0, compare);
    }

検証

さて，こうして作成したヒープソートの性能を検証してみよう。

試験条件

  • 要素数 200,000,000 個のint 型の配列の昇順ソートを行う。マージソートの場合，同サイズの配列がもう一つ必要になることから，32bit プログラムではほぼ上限値である。
    4×200,000,000 bytes = 0x2FAF0800 bytes
  • データの順序は以下の四種類とする。
    • ゼロ
    • 昇順：0 → 199,999,999
    • 降順：199,999,999 → 0
    • 乱数：0～199,999,999 の範囲の一様乱数，乱数発生器は XorShift とした3
  • Cコンパイラは下記の三種類とし，かつターゲットを 32bit (x86)と64bit (x64)の二種類の組み合わせで合計六種類とする。
    • Microsoft Visual C++ 2022
    • LLVM clang 17.0.3
    • intel C++ compiler：oneAPI 2024.2, Compiler Release 2024.2.1
  • 評価マシンのスペックは下記の通り
    Windows10 2022H2，Core i7-13700 5.1GHZ，32GB

比較回数・転送回数の比較

それではヒープソートをクイックソートやマージソートと比べてみよう。まずは比較回数・転送回数の比較である。

表１　比較回数の比較
順序 uCRT
(quicksort)		 heapsort glibc
(mergesort)
ゼロ 399,999,999 599,999,994 2,728,894,208
昇順 5,363,792,412 10,638,025,831 2,728,894,208
降順 5,363,792,412 10,254,682,621 2,802,670,336
乱数 6,400,427,154 10,425,754,985 5,265,836,886
表２　転送回数の比較
順序 uCRT
(quicksort)		 heapsort glibc
(mergesort)
ゼロ 0 699,999,997 5,457,788,416
昇順 265,782,274 6,002,057,276 5,457,788,416
降順 465,782,278 5,691,128,726 11,063,129,088
乱数 2,736,238,624 5,843,143,718 10,752,119,342

グラフにすると一目瞭然であるが，ヒープソートはとにかく比較回数が多い。データがすべてゼロのような特殊データを除き，他ソートの２倍以上を要している。一方，データ転送回数は少なめである。

■uCRT (quicksort)，■heapsort，■glibc (mergesort)

実行時間の比較の比較

次に実行時間の比較を示そう。

表３　実行時間の比較（単位は秒）
コンパイラ 順序 uCRT
(quicksort)		 heapsort glibc
(mergesort)
Visual C++
32bit版		 ゼロ 0.090 0.257 2.660
昇順 1.433 7.015 2.656
降順 1.475 7.171 3.914
乱数 15.505 67.758 17.996
Visual C++
64bit版		 ゼロ 0.093 0.390 2.470
昇順 1.582 12.431 2.473
降順 1.617 13.238 3.769
乱数 15.500 47.003 21.129
LLVM clang-cl
32bit版		 ゼロ 0.098 0.300 2.066
昇順 1.627 9.614 2.060
降順 1.688 10.460 3.642
乱数 15.636 43.639 16.487
LLVM clang-cl
64bit版		 ゼロ 0.089 0.290 1.958
昇順 1.460 10.148 1.997
降順 1.523 10.973 2.942
乱数 15.710 42.842 16.022
intel icx-cl
32bit版		 ゼロ 0.070 0.320 2.488
昇順 1.592 9.687 2.498
降順 1.691 10.517 3.333
乱数 17.120 43.222 17.809
intel icx-cl
64bit版		 ゼロ 0.064 0.307 1.811
昇順 1.366 10.818 1.797
降順 1.491 11.635 2.507
乱数 16.584 42.916 15.969

グラフにすると一目瞭然だが，ヒープソートは他のソートと比べて２倍以上遅いのだ。

■uCRT (quicksort)，■heapsort，■glibc (mergesort)

まとめ

ということで，ヒープソートは平均的な乱数データに対してはクッソ遅いので，積極的に使うことはほぼ無いと思われる。メモリアクセスもシーケンシャルアクセスとなる挿入ソートとは異なり，飛び飛びのランダムアクセスに近い形になるのでとにかくパフォーマンスが上がらない。

そもそもまず最上層が最大値となるように（それなりのコストをかけて）ヒープ構造を作るのにも関わらず，せっかく作ったそのヒープ構造を崩しながらソートを行っていくので，直感的にも２倍のコストをかけているように思える。

ただし，実際に実行時間の大半を占めているのは，関数 heap() の呼び出しのうち二回目のほうである。一回目の呼び出し，すなわち配列全体をヒープ構造に変換する処理自体はあまり処理時間を要していないのだ。

であればヒープソート自体にまだ改善の余地があるようにも思える。たとえば本記事で

まるで新入社員をいきなり社長に抜擢するようなもので一見無駄に見える。

と指摘したように。

参考文献

1
1
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
1
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?