# dis is a PriorityQueue
class PriorityQueue
  def initialize
    clear
  end

  def <<(element)
    @elements << element
    # bubble up the element that we just added
    bubble_up(@elements.size - 1)
  end

  alias push <<

  def peek
    # the first element will always be the min, because of the heap constraint
    @elements[1]
  end

  def pop
    # remove the last element of the list
    min = @elements[1]

    # and make sure the tree is ordered again
    bubble_down(1)
    min
  end

  def clear
    @elements = [nil]
  end

  def empty?
    @elements.length < 2
  end

  private

  def bubble_up(index)
    target = @elements[index]
    loop do
      parent_index = (index / 2)

      # return if we reach the root or the parent is less than the child
      if parent_index < 1 || @elements[parent_index] <= target
        @elements[index] = target
        return
      end

      # otherwise we exchange the child with the parent
      @elements[index] = @elements[parent_index]

      # and keep bubbling up
      index = parent_index
    end
  end

  def bubble_down(index)
    target = @elements.pop
    loop do
      child_index = (index * 2)

      # stop if we reach the bottom of the tree
      if child_index > @elements.size - 1
        @elements[index] = target
        return
      end

      # make sure we get the smallest child
      not_the_last_element = child_index < @elements.size - 1
      left_element = @elements[child_index]
      right_element = @elements[child_index + 1]
      child_index += 1 if not_the_last_element && right_element < left_element

      # there is no need to continue if the parent element is already smaller
      # then its children
      if target <= @elements[child_index]
        @elements[index] = target
        return
      end

      @elements[index] = @elements[child_index]

      # repeat the process until we reach a point where the parent
      # is larger than its children
      index = child_index
    end
  end
end