ヒープソート (heap sort) とはリストの並べ替えを二分ヒープ木を用いて行うソートのアルゴリズムである(ヒープ領域とは無関係であることに注意する)。 アルゴリズムは、以下のように2つの段階から構成される。 1. * 未整列のリストから要素を取り出し、順にヒープに追加する。すべての要素を追加するまで繰り返し。 2. * ルート(最大値または最小値)を取り出し、整列済みリストに追加する。すべての要素を取り出すまで繰り返し。 計算量は O となる。安定ソートではない。