ヒープソート（Heap Sort）とは、「ヒープ」と呼ばれる親子間の値に一定の大小関係ルールがある木構造を利用して、データを並べ替えるアルゴリズムです。ヒープの根（一番上）には必ず最大値（または最小値）が配置されるという特徴を利用し、根にある最大値を取り出して配列の末尾に移動させ、残りのデータで再びヒープを再構築する操作をデータがなくなるまで繰り返します。
バラバラに積まれた複数の箱から、最も重い箱（最大値）を取り出して並べていきます。取り出したあと、残された箱の山から自動的に「次に最も重い箱」が一番上に上がってくる仕組みをヒープで実現し、ソートを行います。
1. 未整理データからヒープ構造を作成（根に最大値がくる）
2. 根の最大値を取り出して、整理済み配列の末尾に移動
3. 残ったデータでヒープを再構築し、再度根から最大値を取り出す
4. 2〜3を全データ分繰り返してソート完了