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

ヒープ構造は、ポインタ等の制御用データが不要で、データ自体の並び順（排列）だけで表現できるという利点がある。ヒープソートを実装する際にはこの利点を生かし、元のデータ領域をそのままヒープ構造や整列済みリストに転用するインプレースなソートとして実装することが多い。
最初にN個のデータを含む配列が与えられるものとする。添字は1 ～ Nとする。
まず各データをヒープ構造に登録していく。m個のデータを処理した状態では、添字1 ～ mがヒープ構造で、(m + 1) ～ Nが未整列リストとなる。m + 1個目のデータを取り出し、ヒープ構造に登録する。このとき構成するヒープは、昇順にソートする場合はルートが最大値になるよう、降順にソートする場合はルートが最小値になるよう構成する。
すべてのデータをヒープ構造に登録し終えたら、ヒープからの取り出しに移る。ヒープのルートを取り出し、配列の後ろから詰めていく。mを Nから1まで減じながら、取り出したルート要素を配列の添字mに置く。すなわち、(N – m)個のデータを取り出した状態では添字1 ? mがヒープ構造であり、m + 1 ～ Nが整列済みリストとなる。
すべてのデータをヒープ構造から取り出し終えると、配列全体が整列済みになる。
ヒープの操作の具体的な実装については、二分ヒープの記事を参照すること。
また、一般のヒープ操作では、根元側から木を成長させるのが普通だが、配列のようなデータ構造のヒープソートで、あらかじめ木の最終的な大きさがわかっている場合は、木の葉の側から順番にヒープを構築すると、より効率が良い（この記事で示す実装例では使っていない）。