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.newqueue<<33queue<<44queue<<1putsqueue.peek# => 44
Attributes
Public Class Methods
Public Instance Methods
Source
# File lib/syntax_suggest/priority_queue.rb, line 26def<<(element)@elements<<elementbubble_up(last_index,element)end
Source
# File lib/syntax_suggest/priority_queue.rb, line 98defexchange(source,target)a =@elements[source]b =@elements[target]@elements[source] =b@elements[target] =aend
Source
# File lib/syntax_suggest/priority_queue.rb, line 31defpopexchange(0,last_index)max =@elements.popbubble_down(0)maxend
Source
# File lib/syntax_suggest/priority_queue.rb, line 55defsortedout = []elements =@elements.dupwhile (element =pop)out<<elementend@elements =elementsout.reverseend
Used for testing, extremely not performant
Private Instance Methods
Source
# File lib/syntax_suggest/priority_queue.rb, line 81defbubble_down(index)child_index = (index*2)+1returnifchild_index>last_indexnot_the_last_element =child_index<last_indexleft_element =@elements[child_index]right_element =@elements[child_index+1]child_index+=1ifnot_the_last_element&& (right_element<=>left_element)==1returnif (@elements[index]<=>@elements[child_index])>=0exchange(index,child_index)bubble_down(child_index)end
Source
# File lib/syntax_suggest/priority_queue.rb, line 69defbubble_up(index,element)returnifindex<=0parent_index = (index-1)/2parent =@elements[parent_index]returnif (parent<=>element)>=0exchange(index,parent_index)bubble_up(parent_index,element)end
Source
# File lib/syntax_suggest/priority_queue.rb, line 65deflast_index@elements.size-1end