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
Attributes
Read
No documentation available
Class Methods
::
lib/syntax_suggest/priority_queue.rb
View on GitHub
# File tmp/rubies/ruby-3.4.0-preview1/lib/syntax_suggest/priority_queue.rb, line 22
def initialize
@elements = []
end
No documentation available
Instance Methods
lib/syntax_suggest/priority_queue.rb
View on GitHub
# File tmp/rubies/ruby-3.4.0-preview1/lib/syntax_suggest/priority_queue.rb, line 26
def <<(element)
@elements << element
bubble_up(last_index, element)
end
No documentation available
lib/syntax_suggest/priority_queue.rb
View on GitHub
# File tmp/rubies/ruby-3.4.0-preview1/lib/syntax_suggest/priority_queue.rb, line 81
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
No documentation available
lib/syntax_suggest/priority_queue.rb
View on GitHub
# File tmp/rubies/ruby-3.4.0-preview1/lib/syntax_suggest/priority_queue.rb, line 69
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
No documentation available
#
lib/syntax_suggest/priority_queue.rb
View on GitHub
# File tmp/rubies/ruby-3.4.0-preview1/lib/syntax_suggest/priority_queue.rb, line 42
def empty?
@elements.empty?
end
No documentation available
lib/syntax_suggest/priority_queue.rb
View on GitHub
# File tmp/rubies/ruby-3.4.0-preview1/lib/syntax_suggest/priority_queue.rb, line 98
def exchange(source, target)
a = @elements[source]
b = @elements[target]
@elements[source] = b
@elements[target] = a
end
No documentation available
lib/syntax_suggest/priority_queue.rb
View on GitHub
# File tmp/rubies/ruby-3.4.0-preview1/lib/syntax_suggest/priority_queue.rb, line 65
def last_index
@elements.size - 1
end
No documentation available
#
lib/syntax_suggest/priority_queue.rb
View on GitHub
# File tmp/rubies/ruby-3.4.0-preview1/lib/syntax_suggest/priority_queue.rb, line 38
def length
@elements.length
end
No documentation available
#
lib/syntax_suggest/priority_queue.rb
View on GitHub
# File tmp/rubies/ruby-3.4.0-preview1/lib/syntax_suggest/priority_queue.rb, line 46
def peek
@elements.first
end
No documentation available
#
lib/syntax_suggest/priority_queue.rb
View on GitHub
# File tmp/rubies/ruby-3.4.0-preview1/lib/syntax_suggest/priority_queue.rb, line 31
def pop
exchange(0, last_index)
max = @elements.pop
bubble_down(0)
max
end
No documentation available
#
lib/syntax_suggest/priority_queue.rb
View on GitHub
# File tmp/rubies/ruby-3.4.0-preview1/lib/syntax_suggest/priority_queue.rb, line 55
def sorted
out = []
elements = @elements.dup
while (element = pop)
out << element
end
@elements = elements
out.reverse
end
Used for testing, extremely not performant
#
lib/syntax_suggest/priority_queue.rb
View on GitHub
# File tmp/rubies/ruby-3.4.0-preview1/lib/syntax_suggest/priority_queue.rb, line 50
def to_a
@elements
end
No documentation available