ヒープソート（Heap Sort）は、木構造の一種である「ヒープ（特に最大ヒープ）」を用いて、効率的に整列を行うアルゴリズムです。手順は大きく分けて2つのフェーズからなります。まずヒープ構築フェーズでは、ソート対象の配列全体を、親ノードの値が子ノードの値以上になる「最大ヒープ」構造に並べ替えます。この段階で、配列の先頭（ヒープの根）には全体の最大値が位置することになります。次にソートフェーズでは、根にある最大値（配列の先頭要素）と、未整列部分の末尾要素を入れ替えます。これにより、最大値が配列の末尾に確定します。次に、残された未整列部分（サイズが1減った配列）に対して、再度根からヒープ構造を再構築（ヒープ化）します。これにより次に大きい値が根に浮上します。この「最大値の確定とヒープ再構築」を、未整列部分の要素がなくなるまで繰り返します。ヒープソートは、最悪・最良・平均すべてのケースで時間計算量が O(N log N) となり、マージソートと違って追加のメモリ領域を必要としない（インプレースで動作する、領域計算量 O(1)）という優れた長所を持っています。しかし、同値の要素の順序が維持されない「不安定ソート」であり、またメモリ上の離れた位置にある要素を頻繁に入れ替えるため、キャッシュメモリの有効利用（参照の局所性）が効きにくく、実質的な実行速度はクイックソートよりも遅くなる傾向があります。