class SyntaxSuggest::PriorityQueue
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
elements
[R]
Public Class Methods
new
()
# File lib/syntax_suggest/priority_queue.rb, line 22 def initialize @elements = [] end
Public Instance Methods
<<
(element)
# File lib/syntax_suggest/priority_queue.rb, line 26 def <<(element) @elements << element bubble_up(last_index, element) end
empty?
()
# File lib/syntax_suggest/priority_queue.rb, line 42 def empty? @elements.empty? end
exchange
(source, target)
# File 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
length
()
# File lib/syntax_suggest/priority_queue.rb, line 38 def length @elements.length end
peek
()
# File lib/syntax_suggest/priority_queue.rb, line 46 def peek @elements.first end
pop
()
# File lib/syntax_suggest/priority_queue.rb, line 31 def pop exchange(0, last_index) max = @elements.pop bubble_down(0) max end
sorted
()
Used for testing, extremely not performant
# File 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
to_a
()
# File lib/syntax_suggest/priority_queue.rb, line 50 def to_a @elements end