基本情報技術者 予想問題｜A 第16問

解説

正解はウ。ヒープソートは、「親ノードの値が子ノードの値以上（最大ヒープ）または以下（最小ヒープ）」という性質を満たす完全二分木である二分ヒープを利用する整列アルゴリズムである。手順は、①配列全体をヒープに構築する、②根（最大値または最小値）を取り出して末尾の要素と交換する、③ヒープの性質を回復させる、を繰り返すことで整列が完成する。ヒープ構築がO(n)、n回の取出しがそれぞれO(log n)であるため、全体の計算量は最悪でもO(n log n)であり、追加メモリをほとんど使わない点が特徴である。アのスタックはLIFO、イのキューはFIFOの構造で整列の中核には用いず、エの連結リストもヒープソートの基盤ではない。基本情報では、ヒープの性質（根が最大・最小）と、優先度付きキューへの応用が頻出ポイントである。