🔍

No recent searches

# 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 ()
Source

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

### Public Instance Methods

<< (element)
Source

    # File lib/syntax_suggest/priority_queue.rb, line 26
    def <<(element)
      @elements << element
      bubble_up(last_index, element)
    end

empty? ()
Source

    # File lib/syntax_suggest/priority_queue.rb, line 42
    def empty?
      @elements.empty?
    end

exchange (source, target)
Source

    # 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 ()
Source

    # File lib/syntax_suggest/priority_queue.rb, line 38
    def length
      @elements.length
    end

peek ()
Source

    # File lib/syntax_suggest/priority_queue.rb, line 46
    def peek
      @elements.first
    end

pop ()
Source

    # File lib/syntax_suggest/priority_queue.rb, line 31
    def pop
      exchange(0, last_index)
      max = @elements.pop
      bubble_down(0)
      max
    end

sorted ()
Source

    # 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

Used for testing, extremely not performant

to_a ()
Source

    # File lib/syntax_suggest/priority_queue.rb, line 50
    def to_a
      @elements
    end

### Private Instance Methods

bubble_down (index)
Source

    # 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)
Source

    # 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 ()
Source

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