ヒープソート

ヒープ構造とは

木構造の一種

二分木の各節点にデータ値を保存して、親のデータが2つの子データよりも小さくなるように作られたデータ構造

一番の親(根)は必ず最小値のデータになる

ヒートソートの手順

与えられたデータでヒープ構造を作る

「根」を取り出して、残りのデータで再びヒープ構造を作り「根」を除外するという操作を繰り返す

計算量はヒープ構造を作るのにlogn回の計算、「根」の取り出しはn回なので、全体として計算量はO(nlogn)となる

関連記事