Priority queue in ruby.rb

class PriorityQueue
  attr_reader :elements

  def initialize
    @elements = []
  end

  def <<(element)
    @elements << element
    bubble_up(last_index, element)
  end

  def pop
    exchange(0, last_index)
    max = @elements.pop
    bubble_down(0)
    max
  end

  def length
    @elements.length
  end

  def empty?
    @elements.empty?
  end

  def peek
    @elements.first
  end

  def to_a
    @elements
  end

  # Used for testing, extremely not performant
  def sorted
    out = []
    elements = @elements.dup
    while element = self.pop
      out << element
    end
    @elements = elements
    out.reverse
  end

  private def last_index
    @elements.size - 1
  end

  private def gt(a, b)
    (a <=> b) == 1
  end

  private def gte(a, b)
    case a <=> b
    when 0, 1
      true
    else
      false
    end
  end

  private def bubble_up(index, element)
    return if index <= 0

    parent_index = (index - 1) / 2
    parent = @elements[parent_index]

    return if gte(parent, element)

    exchange(index, parent_index)
    bubble_up(parent_index, element)
  end

  private 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 && gt(right_element, left_element)

    return if gte(@elements[index], @elements[child_index])

    exchange(index, child_index)
    bubble_down(child_index)
  end

  def exchange(source, target)
    a = @elements[source]
    b = @elements[target]
    @elements[source] = b
    @elements[target] = a
  end
end

x-tests.rb

      q = PriorityQueue.new
      q << 1
      q << 2
      expect(q.elements).to eq([2, 1])


      q << 3
      expect(q.elements).to eq([3, 1, 2])

      out = []
      q.each {|x| out << x }
      expect(out).to eq([3, 2, 1])

      expect(q.pop).to eq(3)
      expect(q.pop).to eq(2)
      expect(q.pop).to eq(1)
      expect(q.pop).to eq(nil)

      array = []
      q = PriorityQueue.new
      array.reverse.each do |v|
        q << v
      end
      expect(q.elements).to eq(array)

      array = [100, 36, 17, 19, 25, 0, 3, 1, 7, 2]
      array.reverse.each do |v|
        q << v
      end

      expect(q.pop).to eq(100)
      expect(q.elements).to eq([36, 25, 19, 17, 0, 1, 7, 2, 3])

      # expected [36, 25, 19, 17, 0, 1, 7, 2, 3]
      expect(q.pop).to eq(36)
      expect(q.pop).to eq(25)
      expect(q.pop).to eq(19)
      expect(q.pop).to eq(17)
      expect(q.pop).to eq(7)
      expect(q.pop).to eq(3)
      expect(q.pop).to eq(2)
      expect(q.pop).to eq(1)
      expect(q.pop).to eq(0)
      expect(q.pop).to eq(nil)