Priority Queue

class PriorityQueue

  attr_accessor :a

  attr_accessor :size
  def initialize(a)
    @a = a
    self.size = a.length
    build_heap
  end

  def push(value)
    a << value
    self.size = a.length
    i = size - 1

    while  (parent_i = parent(i)) && parent_i >= 0 && a[parent_i] > a[i]
      a[parent_i],a[i] = a[i],a[parent_i]
      i = parent_i
    end


  end


  def build_heap
    (size / 2).downto(0) do |i|
      heapify(i)
    end
  end


  def heapify(i)

    left_i = left_child(i)
    right_i = right_child(i)

    smallest_i = i


    if left_i && left_i < size && a[left_i] < a[smallest_i]
      smallest_i = left_i
    end

    if right_i && right_i < size && a[right_i] < a[smallest_i]
      smallest_i = right_i
    end

    if i != smallest_i
      a[i],a[smallest_i] = a[smallest_i],a[i]
      heapify(smallest_i)
    end

  end

  #returns the min and removes it
  def pop
    a[0],a[size-1] = a[size-1],a[0]
    value = a.delete_at(size-1)
    self.size -= 1
    heapify(0)
    value
  end

  #returns the mininum element without deleting it
  def top
    a[0]
  end


  def empty?
    a.empty?
  end
  def sort
    until size == 1
      a[size-1],a[0] = a[0],a[size-1]
      self.size  -= 1
      heapify(0) #log(n)
    end
    self.size = a.length
    a
  end

  private


  def parent(i)
    if i <= 0 || i >= size
      return nil
    else
      (i -1) / 2
    end
  end

  def left_child(i)
    if i >= size
      nil
    else
      i * 2 + 1
    end
  end

  def right_child(i)
    if i >= size
      nil
    else
      i * 2 + 2
    end
  end

end

a1 = [2,5,8, 20, 200]
a2 = [1,9,20, 10, 10]
a3 = [0,4,7, 10, 200]

arrays = [a1,a2,a3]

merge = []
q = PriorityQueue.new([])


class Node
  include Comparable

  attr_accessor :i, :k, :value

  def initialize(i:,k:,value:)
    @i = i
    @k = k
    @value = value
  end

  def <=>(another)
    self.value <=> another.value
  end


end

arrays.each_with_index do |a, k|
  q.push(Node.new(i: 0, value: a[0], k: k))
end


until q.empty?
  e = q.pop
  merge << e.value
  a = arrays[e.k]
  next_i = e.i + 1
  q.push(Node.new(i: next_i, k: e.k, value: arrays[e.k][next_i])) if next_i < a.length
end

puts merge.to_s