1class Heap
 2  def initialize(items = [], sorting = QuickSort.new)
 3    @items = sorting.sort(items.map { |x| Node.new(x, x) })
 4    @sort_strategy = sorting
 5  end
 6
 7  def insert(key, value=key)
 8    node = Node.new(key, value)
 9    @items.push(node)
10    @items = @sort_strategy.sort(@items)
11  end
12
13  def min
14    item = @items.shift
15    item.value if item
16  end
17
18  def max
19    item = @items.pop
20    item.value if item
21  end
22
23  def empty?
24    @items.empty?
25  end
26
27  def self.heapify(items)
28    Heap.new(items)
29  end
30
31  alias_method :push, :insert
32
33  class Node
34    attr_reader :key, :value
35
36    def initialize(key, value)
37      @key = key
38      @value = value
39    end
40
41    def <=>(other_key)
42      other_key <=> @key
43    end
44  end
45end