アルゴリズムとデータ構造 - ヒープ

bmf-san アルゴリズムとデータ構造
#ヒープ

概要

アルゴリズム図鑑を参考に、アルゴリズムとデータ構造を学ぶ。

実装はgithub - bmf-san/road-to-algorithm-masterにも置いてある。

ヒープ

  • 優先度付きキュー（priority queue）の一種
    • 優先度付きキューは、集合（set）を扱うデータ型
      • 集合に含まれる要素は優先度順に取り出される
      • 集合を扱うデータ型の例：キュー、スタック
  • ヒープの種類
    • 最小ヒープ（min heap）
      • 根が常に最小となっているヒープ。親ノードは子ノードより常に小さい。
    • 最大ヒープ（max heap）
      • 根が常に最大の要素となっているヒープ。親ノードは子ノードより常に大きい。

計算時間

  • 追加・削除共にO(log n)

実装

  • 最小ヒープ（min heap）の実装
  • ノードの追加は常に幅優先順で追加される
  • ノード追加後、追加した値が根のノードより小さい場合、根ノードと追加したノードを入れ替える
  • Data Structure Visualizations - Min Heapでイメージを確認するとわかりやすい
  • 根、親、左の子ノード、右の子ノードの計算が特徴的
    • 配列のインデックスが優先度となるので、計算によってそれらのノードの値が基準となるノードから求めることができる
    • ヒープをわかりやすく解説してみたの記事がわかりやすい
  • Welcome To Golang By Example - Heap in Golangを参考にした（ほとんど写経..）

参考