find the kth least common element in an array in ruby

main.rb
def kth_least_common_element(arr, k)
  sorted_arr = arr.sort
  hashmap = Hash.new(0)
  sorted_arr.each { |e| hashmap[e] += 1 }
  heap = Heap.new
  hashmap.each do |key, value|
    heap.add([value, key])
    if heap.size > k
      heap.remove_min
    end
  end
  heap.remove_min[1]
end

class Heap
  def initialize
    @heap = []
  end

  def add(item)
    @heap << item
    up_heap
  end

  def remove_min
    item = @heap[0]
    @heap[0] = @heap.pop
    down_heap
    item
  end

  def size
    @heap.size
  end

  private
  def up_heap
    i = @heap.size - 1
    while has_parent(i) && parent(i)[0] > @heap[i][0]
      swap(i, parent_index(i))
      i = parent_index(i)
    end
  end

  def down_heap
    i = 0
    while has_left_child(i)
      smaller_child_index = left_child_index(i)
      if has_right_child(i) && right_child(i)[0] < left_child(i)[0]
        smaller_child_index = right_child_index(i)
      end

      if @heap[i][0] < @heap[smaller_child_index][0]
        break
      else
        swap(i, smaller_child_index)
      end

      i = smaller_child_index
    end
  end

  def has_parent(index)
    parent_index(index) >= 0
  end

  def has_left_child(index)
    left_child_index(index) < @heap.size
  end

  def has_right_child(index)
    right_child_index(index) < @heap.size
  end

  def parent(index)
    @heap[parent_index(index)]
  end

  def left_child(index)
    @heap[left_child_index(index)]
  end

  def right_child(index)
    @heap[right_child_index(index)]
  end

  def parent_index(index)
    (index - 1) / 2
  end

  def left_child_index(index)
    index * 2 + 1
  end

  def right_child_index(index)
    index * 2 + 2
  end

  def swap(index1, index2)
    temp = @heap[index1]
    @heap[index1] = @heap[index2]
    @heap[index2] = temp
  end
end
1781 chars
105 lines