# 問題解決力を鍛える！アルゴリズムとデータ構造

## 第10.5章~

- 任意参加
- ファシリテーター: tsujita

### 話す・書く順番決めルーレット

in Ruby

['hsu', 'chen', 'teruya', 'kanazawa', 'okura', 'tsujita'].shuffle.each { |v| puts ">[name=#{v}]\n\n" }

in JavaScript

const l = ['hsu', 'chen', 'teruya', 'kanazawa', 'okura', 'tsujita']
l[Math.floor(Math.random()*l.length)]

### ファシリテーター決め方

- `%w(hsu chen teruya kanazawa okura kanno)`の順番でやっていく

### 参加者がやること
- 事前に決められた章を読む
- 学んだことやわからなかったことを書き込む（任意）

当日
- 最初に感想や質問を書く時間を設ける(10分)
- 時間枠 60分
- 延長枠 30分

### 勉強会時にやること

各自学びや気付き、疑問を発表していく
ファシリテーターがよしなに議論を進める
終了前に勉強会を振り返る？（KPTなどで）← 60分のときに仮締め

## 各自が書き込む場所
>[name=tsujita]

- ヒープの部分で高校数学の数列を思い出しました・・・

>[name=teruya]

https://atcoder.jp/contests/past202004-open/tasks/past202004_f

# 最大が最上位の親になる 優先度付きキュー PQ
# 最小が最上位の親にする時は、コメントアウト箇所を変更
# 更新機能
class PriorityQueue
  attr_accessor :data, :size

  def initialize(array = [])
    @data = []
    array.each { |a| push(a) }
  end

  def push(element)
    current = @data.size
    @data[up_heap(current, element)] = element
  end

  def pop
    ret = @data.first
    x = @data.last
    @data[down_heap(0, x)] = x
    @data.pop
    ret
  end

  def update(current, element)
    index = up_heap(current, element)
    index = down_heap(current, element) if index == current
    @data[index] = element
  end

  def size
    @data.size
  end

  def front
    @data.first
  end

  def empty?
    @data.empty?
  end

  def parent(num)
    (num - 1) / 2
  end

  def left_child_index(num)
    2 * num + 1
  end

  def right_child_index(num)
    2 * num + 2
  end

  def have_parent?(index)
    index > 0
  end

  def have_child?(index)
    left_child_index(index) < @data.size
  end

  private

    def up_heap(current, element)
      while have_parent?(current)
        p_index = parent(current)
        break if @data[p_index] >= element
        # break if @data[p_index] <= element
        @data[current] = @data[p_index]
        current = p_index
      end
      current
    end

    def down_heap(current, element)
      while have_child?(current)
        a_index = left_child_index(current)
        b_index = right_child_index(current)
        a_index = b_index if @data[b_index] && @data[b_index] > @data[a_index]
        break if @data[a_index] <= element
        # a_index = b_index if @data[b_index] && @data[b_index] < @data[a_index]
        # break if @data[a_index] >= element
        @data[current] = @data[a_index]
        current = a_index
      end
      current
    end
end

n = gets.to_i
# 初期値がarrayのhash
tasks = Hash.new { |hash, key| hash[key] = [] }
n.times do
  day, point = gets.split.map(&:to_i)
  tasks[day] << point
end
# pp tasks
# {1=>[3], 2=>[2, 4]}

pq = PriorityQueue.new
sum = 0
(1..n).each do |i|
  tasks[i].each { |point| pq.push(point) }
  sum += pq.pop
  puts sum
end

>[name=okura]

### 10.5 木

よく見かけるのは根付き木な気がする。

### 10.6 順序木と二分木

順序木という概念は初めて知った。二分木はよく聞く。強平衡二分木の性質が良いので、なんとかしてデータ構造をそれにしたい（そのためには多少コストをかけてもよい）という感じなのだろうと思った。

### 10.7 ヒープ

ヒープはスタックと対になる感じで「Rubyのしくみ」とかで見かけたことがある。

ヒープはRubyだと何が使われるんだろうと思って調べたけど、あんまり出てこない。
https://github.com/florian/rb_heap

### 10.8 二分探索木

Gemとかはなさそうだけど、自前で割と簡単に書けるのかな。

### おまけ

`RubyVM::AbstractSyntaxTree`に追加したメソッド。

def traverse(*types, &block)
  if block_given?
    children.each do |node|
      yield(node) if node.respond_to?(:type) && (types.empty? || types.include?(node.type))
      node.traverse(*types, &block) if node.respond_to?(:traverse)
    end
  else
    to_enum(:traverse, *types)
  end
end

def parent_of?(other)
  children.map(&:node_id).include?(other.node_id)
end

>[name=chen]

- ヒープは、アルゴリズムとして大体理解できるけど、どこで使われるのがよく分かりないんですね...
- code 10.5 ヒープの実装例、jsで書きました。

const heap = []
let size = heap.length

function heap_push(x){
　heap.push(x)
  let i = size - 1
  while(i > 0) {
  	let p = (i - 1) / 2
    if(heap[p] >= x) break
    heap[i] = heap[p]
    i = p
  }
  heap[i] = x
}

function get_top(){
　if(heap.length > 0) return heap[0]
  else return -1
}

function heap_pop(){
　let size = heap.length
　if(heap.length === 0) return
　let x = heap[heap.length - 1]
　heap.pop()
　let i = 0
  while( i * 2 + 1 < size){
　　let child_1 = i*2 + 1
　　let child_2 = i*2 + 2
　　if(child_2 < heap.length 
    	&& heap[child_2] > heap(child_1))
    {
    	child_1 = child_2
    }
    if(heap[child_1] <= x) break
    i = child_1
  }
  heap[i] = x
} 


heap_push(5)
heap_push(6)
heap_push(1)

console.log("heap : " + heap)
console.log("top : " + get_top())
heap_pop()
console.log("heap : " + heap)
console.log("top : " + get_top())

heap_push(11)

console.log("heap : " + heap)
console.log("top : " + get_top())

// "heap : 5,6,1"
// "top : 5"
// "heap : 5,1"
// "top : 5"
// "heap : 5,1,11"
// "top : 5"

## 振り返り
>[name=tsujita]

せっかく勉強しているので仕事でアルゴリズムを活かしていきたい・・

> [name=teruya]

優先度付きキューでないと対応不可能な課題は少ないと思いますね🧐

>[name=okura]

"heap"

> 積み重ね，堆積（たいせき），山（積み）

> [name=chen]

ヒープの利用できる場合
https://ylb.jp/2006b/proc/heap/
> プログラムが使うメモリ領域として、プログラムの機械語が置かれている領域(プログラム領域、またはテキスト領域)のほかに、静的領域とスタック領域があることはすでに学びました。 この章では、もう1つのメモリ領域であるヒープ領域(heap)について学びます。 ヒープを使うと「必要になった時に必要なぶんだけメモリを確保する」ことができます。

うんん...大学卒業から今まで全く使ったことがないっすね...:thinking_face:

## 終了後ファシリテーターがやること
- 次回のファシリテーターを決める
- hsuさんに確認する
- 読む範囲を決める
- 第11章