夕蛙のなく頃に

データアナリストとして学んだことや趣味で勉強し始めたIoTをアウトプットする

OpenDataStructures第10章を自分用にまとめる(ヒープ)

なにこれ

前回の続き

blog.frogdusk.com

今回は話がガラッと変わって、優先度付きキューの実装の話です。
特殊な二分木であるヒープを使います。
ヒープとは「雑多に積まれたもの」という意味があり、今までの「高度に構造化されて積み上げられたもの」であったBinarySearchTree等とは対照的であるそう。

  • BinaryHeap

優先度付きキュー

要素の集まりからremoveする際に、最小の値を削除して、返します。

f:id:frogdusk:20190725164145p:plain

BinaryHeap

完全二分木を配列を使って表現します。
要素がヒープ順に並ぶように補正をかけます。ヒープ順とは各ノードは上位のノードの値以上であるような順番です。
こうすることでindex=0は常に配列の中で最小値となっているため、優先度付きキューを効率的に表現することができます。

f:id:frogdusk:20190725164159p:plain

  • addする場合
    • 最後尾に加える
    • そしてヒープ性を保つように加えた値と上位のノードの比較を繰り返して上げていく
  • removeする場合
    • index=0を取り出す
    • 最後尾の値をindex=0に置く
    • 最後尾の値はだいたい配列の中で大きめの値が入っているはずで、おそらくヒープ性は満たせていないので、index=0の値と下位のノードを比較し下げていく
  • 性能
    • 完全二分木であり、高さはlog(n)で抑えられているので、add・removeともにO(logn)となる