ヒープソートの練習

heapsort.rb

# ヒープソートの練習
#
# 参考
# - https://ufcpp.net/study/algorithm/col_heap.html
# - https://ufcpp.net/study/algorithm/sort_heap.html

def make_heap(array, last_index)
  while (last_index > 0)
    parent = ((last_index - 1) / 2).floor
    break unless (array[last_index] > array[parent])

    array[last_index], array[parent] = array[parent], array[last_index]

    last_index = parent
  end
end

def pop_heap(array, last_index)
  # ヒープなので、最大値はルートノード
  max = array[0]

  # 再ヒープ
  array[0] = array[last_index]
  parent = 0
  loop {
    child = 2 * parent + 1
    break unless child < last_index

    # 左右の子のうち、大きいほうを child にする（右の子のインデックス = 左の子のインデックス + 1 なので）
    child += 1 if ((child + 1) < last_index) && (array[child] < array[child + 1])

    if (array[parent] < array[child])
      array[child], array[parent] = array[parent], array[child]
    end
    parent = child
  }

  max
end

def heap_sort(array)
  1.upto(array.size - 1) { |i|
    make_heap(array, i)
  }

  (array.size - 1).downto(0) { |i|
    array[i] = pop_heap(array, i)
  }
end

a = [3, 1, 4, 1, 5, 9, 2]
# a = [3, 1, 4, 1, 5, 9, 2, 6]
pp a

heap_sort(a)
pp a