APアルゴリズムとプログラミング · アルゴリズム

ヒープソート

Heap Sort

ひーぷそーと

ヒープ構造を利用したソートアルゴリズム。データからヒープを構築し、最大（最小）要素を繰り返し取り出して整列する。計算量は常にO(n log n)で追加メモリがO(1)だが、キャッシュ効率がクイックソートより劣る。

共有:

他の資格での定義

ヒープ構造を利用した整列アルゴリズム。データをヒープに構築し、最大値（最小値）を取り出す操作を繰り返す。最悪計算量がO(n log n)で安定しており、追加メモリが不要。不安定ソート。

データからヒープ（親が子より常に大きい、または小さい完全2分木）を作り、根にある最大値（または最小値）を取り出して末尾に移し、残りでヒープを作り直すことを繰り返す整列のアルゴリズム。計算量は平均・最悪ともO(n log n)で、作業領域をほとんど使わないが、安定な整列ではない。

データからヒープ（親が子以上の値を持つ完全2分木）を作り、根にある最大値を取り出してヒープを作り直す操作を繰り返して整列するアルゴリズム。最悪でも計算量はO(n log n)で、作業用の領域もほとんど要らない。

Past Exams

過去問で 6 回出題（応用情報技術者試験 4・高度試験午前Ⅰ 2）。うち 3 回は用語そのものを問う問題です。

出典: 独立行政法人情報処理推進機構（IPA）の過去問題。問題文は IPA のサイトの PDF で確認できます。「用語を問う問題」は、この用語の説明や特徴そのものを問う問題です。「選択肢」は、問題文ではなく選択肢に出たものです。用語名で照合しているため、関係の薄い問題が含まれることがあります。