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