# MinHeap — бинарная куча-минимум на массиве
#
# Реализуй класс MinHeap со следующими методами:
#   MinHeap.new          — создать пустую кучу
#   push(x)              — добавить элемент x
#   pop                  — удалить и вернуть минимальный элемент; если куча пуста, вернуть nil
#   peek                 — вернуть минимальный элемент без удаления; если куча пуста, вернуть nil
#   empty?               — true, если куча пуста
#   size                 — количество элементов
#
# Инвариант: в корне всегда минимальный элемент; после любого push/pop куча остаётся валидной.
#
# Представление: храни элементы в обычном массиве @heap.
#   корень             — индекс 0
#   дети узла i        — индексы 2*i + 1 и 2*i + 2
#   родитель узла i    — индекс (i - 1) / 2
#
# Идея операций:
#   push: добавить элемент в конец массива, затем «всплыть» наверх,
#         пока родитель больше (меняем местами с родителем).
#   pop:  запомнить корень, переставить последний элемент на место корня,
#         затем «утопить» вниз, пока есть ребёнок меньше текущего.

class MinHeap
  def initialize
    @data = []
  end

  def push(el)
    @data.push el

    index = @data.size - 1

    loop do
      break if root?(index)

      if parent(index).nil? || parent(index) > el
        swap(index, parent_index(index))
        index = parent_index(index)
      else
        break
      end
    end
  end

  def empty? = @data.empty?

  def peek = @data[0]

  def size = @data.size

  def pop
    return if empty?

    el = @data.pop

    if !empty?
      @data[0] = el
      index = 0

      loop do
        if !left_child(index).nil? && left_child(index) < el
          swap(index, left_child_index(index))
          index = left_child_index(index)
        elsif !right_child(index).nil? && right_child(index) < el
          swap(index, right_child_index(index))
          index = right_child_index(index)
        else
          break
        end
      end
    end

    el
  end

  def left_child_index(index)
    index * 2 + 1
  end

  def right_child_index(index)
    left_child_index(index) + 1
  end

  def parent_index(index)
    (index - 1) / 2
  end

  def left_child(index)
    @data[left_child_index(index)]
  end

  def right_child(index)
    @data[right_child_index(index)]
  end

  def parent(index)
    @data[parent_index(index)]
  end

  def root?(index) = index == 0

  def swap(index1, index2)
    @data[index1], @data[index2] = @data[index2], @data[index1]
  end
end