類別 SyntaxSuggest::PriorityQueue

在插入時以優先順序堆疊中儲存元素

取代不斷呼叫「sort!」的方式，在第一次時就將元素放置在適當的位置

範例

queue = PriorityQueue.new
queue << 33
queue << 44
queue << 1

puts queue.peek # => 44

屬性

elements[R]

公開類別方法

new() 按一下以切換來源

# File lib/syntax_suggest/priority_queue.rb, line 22
def initialize
  @elements = []
end

公開實例方法

<<(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() 按一下以切換來源

用於測試，效能極差

# 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

私人實例方法

bubble_down(index) 按一下以切換來源

# File 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

bubble_up(index, element) 按一下以切換來源

# File 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

last_index() 按一下以切換來源

# File lib/syntax_suggest/priority_queue.rb, line 65
        def last_index
  @elements.size - 1
end