ヒープソートひーぷそーと

ヒープソート（Heap Sort）は、ヒープ（親おやが子こより常つねに大おおきい/小ちいさい木き構造こうぞう）を使つかい、最大値さいだいち（または最小値さいしょうち）を取とり出だしては並ならべていくソートアルゴリズムです。

観点かんてん	ヒープソート
計算けいさん量りょう（最悪さいあくも）	$O(N\log N)$（保証ほしょう）
追加ついかメモリ	不要ふよう（in-place）
安定あんてい性せい	不安定ふあんてい
強つよみ	最悪さいあく保証ほしょう＋省しょうメモリ

データをいったんヒープに構築こうちくし、根ね（最大値さいだいち）を取とり出だして末尾まつびに置おく操作そうさを繰くり返かえします。クイックソートくいっくそーと と違ちがい最悪さいあくでも $O(N\log N)$ を保証ほしょうし、マージソートまーじそーと と違ちがい追加ついかメモリが不要ふようなため、リアルタイム性せいが求もとめられる場面ばめんや組込くみこみシステムに適てきします。

試験しけんでは 「ヒープ構造こうぞうを使つかう」「最悪さいあくも $O(N\log N)$」「追加ついかメモリ不要ふよう」の 3 点てんが他たのソートとの区別くべつポイントです。