# Heap Implementation
# Jungtaek Lim(Heart), 2009-03-04

class HeapNode
  attr_accessor :key, :value

end

class Heap

  def initialize(is_max_heap)
    @is_max_heap = is_max_heap

    @memory = []
    @last_index = 0
  end

  def insert_data(key, value)
    node = HeapNode.new
    node.key = key
    node.value = value

    @last_index += 1

    @memory[@last_index] = node

    @current_index = @last_index
    @parent_index = @current_index / 2

    while @parent_index != 0
      if true == check_swap_by_index(@parent_index, @current_index)
        swap_node(@parent_index, @current_index)
      end
      

      @current_index = @parent_index
      @parent_index = @current_index / 2
    end
    
  end

  def delete_data
    return nil if @last_index == 0

    ret_node = @memory[1]

    last_node = @memory[@last_index]

    @memory[1] = last_node
    @last_index -= 1

    current_index = 1

    while current_index < @last_index
      left_child_index = current_index * 2
      right_child_index = current_index * 2 + 1

      parent_key = @memory[current_index].key

      if left_child_index  > @last_index
        left_key = (true == @is_max_heap ? -9999999 : 9999999)
      else
        left_key = @memory[left_child_index].key
      end

      if right_child_index > @last_index
        right_key = (true == @is_max_heap ? -9999999 : 9999999)
      else
        right_key = @memory[right_child_index].key
      end
      
      if true == check_max_or_min(left_key, parent_key) &&
          true == check_max_or_min(left_key, right_key)
        swap_node(left_child_index, current_index)

        current_index = left_child_index
      elsif true == check_max_or_min(right_key, parent_key) &&
          true == check_max_or_min(right_key, left_key)
        swap_node(right_child_index, current_index)

        current_index = right_child_index
      else
        break
      end

    end

    return ret_node
  end

  def print_data
    print "["

    (1..@last_index).each do |i|
      print "(" + @memory[i].key.to_s + "," + @memory[i].value.to_s + ")"
    end

    puts "]"
  end

  private

  def check_max_or_min(key1, key2)
    if @is_max_heap
      return (key1 >= key2 ? true : false)
    else
      return (key1 <= key2 ? true : false)
    end
  end

  def check_swap_by_index(parent_index, current_index)
    if @is_max_heap
      return (@memory[@parent_index].key <= @memory[@current_index].key ? true : false)
    else
      return (@memory[@parent_index].key >= @memory[@current_index].key ? true : false)
    end
  end

  def swap_node(index1, index2)
    temp = @memory[index1]
    @memory[index1] = @memory[index2]
    @memory[index2] = temp
  end

end

def make_example_max_heap
  heap = Heap.new(true)
  
  heap.insert_data(8, 0)
  heap.insert_data(13, 0)
  heap.insert_data(10, 0)
  heap.insert_data(15, 0)
  heap.insert_data(19, 0)
  heap.insert_data(20, 0)

  return heap
end

heap = make_example_max_heap
heap.insert_data(17, 0)
heap.print_data

heap = make_example_max_heap
heap.insert_data(23, 0)
heap.print_data

heap = make_example_max_heap
heap.insert_data(14, 0)
heap.print_data
heap.delete_data
heap.print_data