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

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

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

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

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