テクノロジ
ヒープソートとは
読み方：ヒープソート
ひとことで言うと：ヒープの根から最大・最小要素を順に取り出して整列する方法。
意味をわかりやすく解説
ヒープソートは、データを最大ヒープまたは最小ヒープに構成し、根にある最大値または最小値を順に取り出して整列する方法です。
完全二分木を配列で表現でき、時間計算量は最悪でもO(n log n)です。通常は安定ソートではありません。
具体例
昇順に並べる最大ヒープでは、根の最大値を配列末尾と交換し、残りの範囲を再びヒープ化する操作を繰り返します。
似た用語との違い
覚え方
ヒープの根には最大または最小が来る。その根を1個ずつ確定させます。
基本情報技術者試験の試験ポイント
ヒープ構造、親子添字、最悪O(n log n)を押さえます。
CHECK QUESTION
最大ヒープを使うヒープソートで、各回最初に取り出せる要素はどのような値ですか。
答えを見る
ヒープ内の最大値です。最大ヒープでは根が最大値になります。
この説明は分かりやすかったですか？
基本情報技術者試験を勉強中ですか？
この用語を含む重要用語を、単語帳や4択テストで学習できます。