アルゴリズムとデータ構造の要点メモ in ruby（ヒープ）

目的

技術面接のために修行を始める。
ウェブでの技術試験時にみやすいようにこのページにまとめる。
Rubyでそそくさと実装できることを目的とする。

配列 https://qiita.com/tsnb/items/983c32d83331de1e0bea
連結リスト https://qiita.com/tsnb/items/3028ee788ff77ebaaa5e
スタック https://qiita.com/tsnb/items/e6901249629ef090ee8f
キュー https://qiita.com/tsnb/items/588afe675ad830ff1fc6
二分木 https://qiita.com/tsnb/items/8aa4e1ebb24d87919c40
二分探索木 https://qiita.com/tsnb/items/8553f8c2effb4d704d9a

参考

• https://programming-place.net/ppp/contents/algorithm/index.html#header (分かりやすいです、書いた人あざます、この記事をRuby用にまとめてるだけです)

ヒープ（データ構造）

要点

ヒープは、木構造の一種で、格納されているすべての要素の中から、最小値または最大値を持つ要素を探すことに適した構造。

ヒープは、根が最小値、または最大値となるように構成します。根が最小値とした場合、ある節の値は必ずその親以上の値です

実装

• 配列で実装
• バイナリヒープ （以下はO(1)で検索可能）
  • 左の子は、親の値 * 2
  • 右の子は、親の値 * 2 + 1
  • 自分の親は、自分の値 / 2 (余りが出たら切り捨てる)
  • 自分の兄弟は、自分の値 - 1 か + 1
  • 根と最後の要素
• 要素の追加と削除を実装

class Heap
  attr_reader :list

  def initialize
    @list = [nil]
  end

  def add(val)
    @list.push(val)
    up_heap(@list.size - 1)
    @list
  end

  def del(index=1)
    return if index < 1
    @list.swap!(index, -1)
    @list.pop
    down_root(index)
    @list
  end

private
  def up_heap(index)
    return if index <= 1
    parent_index = index/2
    if @list[parent_index] > @list[index]
      @list.swap!(parent_index, index)
      up_heap(parent_index)
    end
  end

  def down_root(index)
    child_index = small_child(index)
    return if child_index >= @list.size
    if @list[index] > @list[child_index]
      @list.swap!(index, child_index)
      down_root(child_index)
    end
  end

  def small_child(index)
    left = index*2
    right = index*2 + 1
    return left if @list[right].nil?
    return right if @list[left].nil?
    (@list[left] > @list[right])? right : left
  end
end

class Array
  def swap!(a, b)
    self[a], self[b] = self[b], self[a]
    self
  end
end

以下のpdfと同じ構造のヒープを作成して、要素削除を実施
http://www.dais.is.tohoku.ac.jp/~shioura/teaching/ad09/ad09-04.pdf

irb(main):303:0> h = Heap.new
=> #<Heap:0x00007fdbfc85ad60 @list=[nil]>
irb(main):304:0> h.add(2)
=> [nil, 2]
irb(main):305:0> h.add(7)
=> [nil, 2, 7]
irb(main):306:0> h.add(4)
=> [nil, 2, 7, 4]
irb(main):307:0> h.add(9)
=> [nil, 2, 7, 4, 9]
irb(main):308:0> h.add(7)
=> [nil, 2, 7, 4, 9, 7]
irb(main):309:0> h.add(4)
=> [nil, 2, 7, 4, 9, 7, 4]
irb(main):310:0> h.add(12)
=> [nil, 2, 7, 4, 9, 7, 4, 12]
irb(main):311:0> h.del
=> [nil, 4, 7, 4, 9, 7, 12]
irb(main):312:0> h.del(3)
=> [nil, 4, 7, 12, 9, 7]