Motivation

ヒープソート（Heap Sort）は、二分ヒープを使用して残りの最大要素を O(log n) の時間で繰り返し見つけることで、信頼性の高い O(n log n) のソートを実現します。

なぜヒープソートを学ぶのか？

• 保証された O(n log n): クイックソートとは異なり、最悪の場合でも O(n²) になることはありません。
• インプレース（In-place）: マージソートとは異なり、元の配列内でソートを行い、追加のメモリは O(1) しか必要としません。
• ヒープの直感的な理解: ヒープが配列にどのように格納されるか、そして sift-down 操作がどのようにヒープの有効性を維持するかについての理解を深めることができます。

このシリーズのヒープに関するコースをすでに学習されている場合、ヒープソートはそのデータ構造をソートアルゴリズムとして活用したものだと理解できるでしょう。