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