minheap.rb

class MinHeap
    def initialize (arr = [])
        @arr = arr.dup.sort!
    end
    
    def push(v)
        i = @arr.size
        @arr.push(v)
        upheap(i)
    end
    
    def pop
        return @arr.pop if @arr.size < 2
        top = @arr[0]
        @arr[0] = @arr.last
        @arr.pop
        downheap(0)
        return top
    end
    
    def pushpop(v)
        top = @arr[0]
        @arr[0] = v
        downheap(0)
        return top
    end
    
    def empty?
        @arr.empty?
    end
    
    def upheap(n)
        p, v = (n-1).div(2), @arr[n]
        while n != 0 && (@arr[p] <=> @arr[n]) == 1
            @arr[n] = @arr[p]
            n, p = p, (p-1).div(2)
        end
        @arr[n] = v
    end
    
    def downheap(n)
        c, len, v = 2*n+1, @arr.size, @arr[n]
        while c < len
            if c+1 < len then
                c += 1 if (@arr[c] <=> @arr[c+1]) == 1
            end
            break if (v <=> @arr[c]) < 0
            @arr[n] = @arr[c]
            n, c = c, 2*c+1
        end
        @arr[n] = v
    end
    
    protected :upheap, :downheap
end