blob: 1abda2a444d0cdcb2e751fd57bfef9902dd09efb (
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
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
99
100
101
102
103
104
105
|
# frozen_string_literal: true
module SyntaxSuggest
# Holds elements in a priority heap on insert
#
# Instead of constantly calling `sort!`, put
# the element where it belongs the first time
# around
#
# Example:
#
# queue = PriorityQueue.new
# queue << 33
# queue << 44
# queue << 1
#
# puts queue.peek # => 44
#
class PriorityQueue
attr_reader :elements
def initialize
@elements = []
end
def <<(element)
@elements << element
bubble_up(last_index, element)
end
def pop
exchange(0, last_index)
max = @elements.pop
bubble_down(0)
max
end
def length
@elements.length
end
def empty?
@elements.empty?
end
def peek
@elements.first
end
def to_a
@elements
end
# Used for testing, extremely not performant
def sorted
out = []
elements = @elements.dup
while (element = pop)
out << element
end
@elements = elements
out.reverse
end
private def last_index
@elements.size - 1
end
private def bubble_up(index, element)
return if index <= 0
parent_index = (index - 1) / 2
parent = @elements[parent_index]
return if (parent <=> element) >= 0
exchange(index, parent_index)
bubble_up(parent_index, element)
end
private def bubble_down(index)
child_index = (index * 2) + 1
return if child_index > last_index
not_the_last_element = child_index < last_index
left_element = @elements[child_index]
right_element = @elements[child_index + 1]
child_index += 1 if not_the_last_element && (right_element <=> left_element) == 1
return if (@elements[index] <=> @elements[child_index]) >= 0
exchange(index, child_index)
bubble_down(child_index)
end
def exchange(source, target)
a = @elements[source]
b = @elements[target]
@elements[source] = b
@elements[target] = a
end
end
end
|
