#
# Heap
#
class Heap
  def initialize(start=[])           ## [] は空の配列、=で引数の即定値を指定
    @size = start.length
    @array = start
    @array[0], @array[@size] = nil, @array[0]   # @array[0] は使わない
    heapify_all
  end

 private
  def heapify_up (here)
    while here > 1
      parent = here.div 2            ## here/2 は整数とは限らない
      break  if @array[parent] >= @array[here]    # 整理完了
                                     ## break で while を脱出
      @array[parent], @array[here] = @array[here], @array[parent]
                                     ## 同時代入で交換が簡単
      here = parent                  # 親のところで繰り返し
    end
  end

  def heapify_down (here)
    while (child=here*2) <= @size
      if child<@size and @array[child]<=@array[child+1]
        child += 1                   # 交換の候補の番号を選択
      end
      break  if @array[here] >= @array[child]
      @array[here], @array[child] = @array[child], @array[here]
      here = child                   # 子のところで繰り返し
    end
  end

  def heapify_all                    # 配列全体を下からヒープにする
    (@size.div 2).downto 1 do |position|
      heapify_down position
    end
  end

 public
  def dup                            # コピーを作る
    duplicate = Heap.new
    duplicate.instance_variable_set :@size, @size
    duplicate.instance_variable_set :@array, @array.dup
    duplicate
  end

  def insert(item)
    @size += 1
    @array[@size] = item             # 今までの配列の後への挿入により、heap を一項目拡大
    heapify_up @size                 # 普遍条件の修復
    self                             ## 他に返すものがなかったら self を返すことが多い
  end                                # heap.insert(x).insert(y) が書けるようになる

  def insert_many(*a)                # * で複数の引数を一つの配列で吸収
    a.each { |item| insert item }
    self
  end

  def find_max()
    @array[1]
  end

  def get_next()
    result = @array[1]
    @array[1] = @array[@size]
    @size -= 1                       # 配列を最後の項目から縮小
    heapify_down 1                   # 普遍条件の修復
    result
  end

  def empty? ()  @size == 0  end
  def length ()  @size  end

  def change(position, new_item)
    old_item = @array[position]
    @array[position] = new_item
    if new_item < old_item
      heapify_down position
    else
      heapify_up position
    end
    self
  end

  def sort
    dup.sort!                        # 現在のヒープを破壊しないよう、dup でコピー
  end

  def sort!                          # ヒープを (その場で) 破壊的にソート
    while @size > 0                  # > 1 で結果が合うが、空にした方がいい
      @array[1], @array[@size] = @array[@size], @array[1]
      @size -= 1
      heapify_down 1
    end
    @array.drop(1)                   # 最初の nil を除去
  end

  def Heap.sort(array)               ## クラス名を指定→クラスメソッド
    Heap.new(array).sort             ## (インスタンスなしで呼出可能)
  end
end

class Array
  def heap_sort ()  Heap.sort(self)    end
  def heap_sort!()  replace heap_sort  end  ## replace は配列の全部の値を上書き
end