通信用語の基礎知識 IPv4
戻る
参加者募集中

ヒープソート

辞書:科学用語の基礎知識 算数・数学編 (NMATH)
読み:ヒープソート
外語:heap sort 英語
品詞:名詞

記事の有効期限について

この記事は更新履歴情報のない、旧形式項目です。久しく更新されておらず、古い記述を含む可能性があります。

更新すべき内容を見つけた場合は、ページ末の報告フォームよりお知らせください。また、現在当サイトは編集仲間を求めています

ヒープを利用したソート。最悪計算量はO(n log n)。

数列の並び方がどのようであっても、安定した処理時間を持つ。

ヒープソートの手順
1. ソートを始める前に配列をヒープ化する
               87
               │
       ┌───┴───┐
       │              │
       59              67
       │              │
   ┌─┴─┐      ┌─┴─┐
   │      │      │      │
   50      38      54      29
   │      │      │
 ┌┴┐  ┌┴┐  ┌┘
 │  │  │  │  │
 43  35  15  11  8
  
2. 一番最初の節点(87)と一番最後の節点(8)の値を入れ替え, 一番最後
   の節点の値はソート済みとする
               8
               │
       ┌───┴───┐
       │              │
       59              67
       │              │
   ┌─┴─┐      ┌─┴─┐
   │      │      │      │
   50      38      54      29
   │      │
 ┌┴┐  ┌┴┐
 │  │  │  │
 43  35  15  11  87
  
3. 木全体を再びヒープ化する
               67
               │
       ┌───┴───┐
       │              │
       59              54
       │              │
   ┌─┴─┐      ┌─┴─┐
   │      │      │      │
   50      38      8      29
   │      │
 ┌┴┐  ┌┴┐
 │  │  │  │
 43  35  15  11  87
  
4. 2.に戻る. 以下すべての節点がソート済みになるまで続ける.
               11
               │
       ┌───┴───┐
       │              │
       59              54
       │              │
   ┌─┴─┐      ┌─┴─┐
   │      │      │      │
   50      38      8      29
   │      │
 ┌┴┐  ┌┘
 │  │  │
 43  35  15  67  87
関連する用語
ソート
ヒープ
アルゴリズム

コメントなどを投稿するフォームは、日本語対応時のみ表示されます


KisoDic通信用語の基礎知識検索システム WDIC Explorer Version 7.03 (16-May-2019)
Search System : Copyright © Mirai corporation
Dictionary : Copyright © WDIC Creators club