703. Kth Largest Element in a Stream - #53

require "benchmark"

def native_insert(ary, num)
  ary.insert(50, num)
end

def ruby_insert(ary, num)
  ary << 0
  (ary.size - 1).downto(50) do |i|
    ary[i + 1] = ary[i]
  end
  ary[50] = num
end

BASE = Array.new(10_000, 0)
N = 10 ** 3
Benchmark.bmbm(10) do |x|
  x.report("insert (native Array#insert)") do
    arr = BASE.dup
    N.times do
      native_insert(arr, 99)
    end
  end
  x.report("ruby_array_inset") do
    arr = BASE.dup
    N.times do
      ruby_insert(arr, 99)
    end
  end
end

        smallest = parent
        left = left_child_index(parent)
        smallest = left if left < @heap.size && @heap[smallest] > @heap[left]
        right = right_child_index(parent)
        smallest = right if right < @heap.size && @heap[smallest] > @heap[right]

        if has_left_child?(smallest)
            left = left_child_index(smallest)
            smallest = left if @heap[left] < @heap[smallest]
        end

class MinHeap
    def initialize
        @heap = []
    end

    def peek
        @heap.first
    end

    def push(val)
        @heap << val
        sift_up(@heap.size - 1)
    end

    def pop
        return nil if @heap.empty?

        swap(0, @heap.size - 1)
        min = @heap.pop
        sift_down(0)
        min
    end

    def size
        @heap.size
    end

    private

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

    def left_child_index(index)
        2 * index + 1
    end

    def right_child_index(index)
        2 * index + 2
    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 has_child?(index)
        has_left_child?(index)
    end

    def smaller_child_index(index)
        smaller_child_index = left_child_index(index)
        if has_right_child?(index) && @heap[left_child_index(index)] > @heap[right_child_index(index)]
            smaller_child_index = right_child_index(index)
        end
        smaller_child_index
    end

    def sift_up(child)
        parent = parent_index(child)
        return if parent < 0 || @heap[parent] <= @heap[child]

        swap(child, parent)
        sift_up(parent)
    end

    def sift_down(parent)
        return unless has_child?(parent)
        smaller_child = smaller_child_index(parent)
        return if @heap[parent] <= @heap[smaller_child]

        swap(parent, smaller_child)
        sift_down(smaller_child)
    end

    def swap(index1, index2)
        @heap[index1], @heap[index2] = @heap[index2], @heap[index1]
    end
end

k = KthLargest.new(3, [])
k.add(3) #=> 3を返す