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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
| class Heap
def initialize
# @elements is an array representing the tree
# for each i:
# parent => @elements[i / 2]
# left => @elements[i * 2]
# right => @elements[i * 2 + 1]
@elements = []
end
def empty
return @elements.count == 0
end
def pop_min
value = @elements[0].first
# Replace the [0]th element with the last one and bubble it down
pair = @elements.pop
# If it was the last element of the array, abort anyway
if @elements.count > 0
@elements[0] = pair
self.bubble_down pair, 0
end
return value
end
def peek_min
return @elements[0].first
end
def push(object, order)
# Put the element at the end of the array and bubble it up the tree
offset = @elements.count
pair = [object, order]
@elements << pair
self.bubble_up pair, offset
end
def bubble_up(pair, offset)
# Push an element up the tree, if need be
parent = offset / 2
while (offset > 0 && @elements[parent].last > pair.last)
@elements[parent], @elements[offset] = @elements[offset], @elements[parent]
offset = parent
parent = offset / 2
end
end
def bubble_down(pair, offset)
# Push an element down the tree if need be
while (offset < @elements.count / 2)
offset_a = offset * 2
offset_b = offset_a + 1
if @elements[offset_a].last > @elements[offset_b].last
smallest = offset_b
else
smallest = offset_a
end
if pair.last <= @elements[smallest].last
break
end
@elements[offset], @elements[smallest] = @elements[smallest], @elements[offset]
offset = smallest
end
end
end
h = Heap.new
# Insert 'a' => 'o' in the heap, random order
h.push "g", 7
h.push "m", 13
h.push "k", 11
h.push "d", 4
h.push "c", 3
h.push "n", 14
h.push "b", 2
h.push "f", 6
h.push "a", 1
h.push "j", 10
h.push "i", 9
h.push "e", 5
h.push "o", 15
h.push "h", 8
h.push "l", 12
# Dump the heap
while !h.empty
puts h.pop_min
end
|