常に子よりも親が大きい（小さい）値の二分木をヒープという。

常に子よりも親が大きい（小さい）値の二分木をヒープという。

2分木を配列で表現すると各要素の位置関係は
n の親は　n - 1 / 2
n の左の子は 2 * n + 1
n の右の子は 2 * (n + 1)
となる。

       0
       |
    +--+--+
    1     2
    |     |
  +-+-+ +-+-+
  |   | |   |
  3   4 5   6 

[0,1,2,3,4,5,6]

S式で表現すると以下になる。

(0  ;; 0 には 1 と 2 の子がある。 
   (1 
     (3 * *) 
     (4 * *)) 
   (2 
     (5 * *)
     (6 * *)))

ヒープの条件を満たしながらデータを追加していく。

def parent(n); (n - 1) / 2 end

def array_swap(array,a,b)
  array[a],array[b] = array[b],array[a]
  array
end

def array_ifswap(array,a,b)
  array[a] > array[b] ? array_swap(array,a,b) : array
end

# 親より値が大きかれば値を交換。
def change(array,pos)
  if pos.zero?
    array 
  else 
    new_p = parent(pos)
    change(array_ifswap(array, pos, new_p), new_p)
  end
end

# ヒープに値を追加。
def pushHeap(array, elem)
  change(array.push(elem), array.size-1)
end

# 二分木をS式で表示
def show_tree(array, length, n)
  "(#{array[n]} " +
  show_leaf(array, length, 2 * n + 1) +
  show_leaf(array, length, 2 * (n + 1)) +  ")"
end

def show_leaf(array, length, pos)
  pos <= length ? show_tree(array, length, pos) : "e "
end


array = []
10.times do
 p pushHeap(array, rand(100))
end

#=>
[45]
[45, 14]
[55, 14, 45]
[55, 44, 45, 14]
[55, 44, 45, 14, 24]
[55, 44, 45, 14, 24, 13]
[55, 44, 45, 14, 24, 13, 38]
[81, 55, 45, 44, 24, 13, 38, 14]
[81, 76, 45, 55, 24, 13, 38, 14, 44]
[90, 81, 45, 55, 76, 13, 38, 14, 44, 24]

puts show_tree(array, array.size, 0)
#=>
(90 (81 (55 (14 e e )(44 e e ))(76 (24 e e )( e e )))
    (45 (13 e e )(38 e e )))

90の子は81と45、81の子は55と76・・・と条件を満たしている。