Ruby Heap

heap.rb

class Heap
    def initialize(a=[],cp=Proc.new{|l,r|l<r})
        @data = a.sort
        @cp = cp
    end
    def empty?
        @data.empty?
    end
    def top
        @data[0]
    end
    def pop
        _swap(0,-1)
        i=0
        while i*2+2 < @data.size
            l = i*2 + 1
            r = i*2 + 2
            if r<@data.size-1 && @cp.(@data[r],@data[l])
                if @cp.(@data[r],@data[i])
                    _swap(i,r)
                    i=r
                else
                    break
                end
            else
                if @cp.(@data[l],@data[i])
                    _swap(i,l)
                    i=l
                else
                    break
                end
            end
        end
        return @data.pop
    end
    def push(e)
        @data.push(e)
        i=@data.size-1
        while 0<i
            t = (i-1)/2
            if @cp.(@data[i],@data[t])
                _swap(i,t)
                i=t
            else
                break
            end
        end
        return self
    end
    def shrink!(s)
        return nil if @data.size<=s
        @data.pop(@data.size-s)
    end
    def _swap(i,j)
        @data[i],@data[j] = @data[j],@data[i]
    end
end

10.times{
    h = Heap.new
    10.times{h.push(rand(0..99))}
    while (!h.empty?);printf "%3d",h.pop;end
    puts ""
}

2000.times{
    h = Heap.new
    100.times{h.push(rand(0..1000))}
    l=h.pop
    while (!h.empty?)
        c=h.pop
        if (l>c);puts "assert: #{l} > #{c}";exit;end
        l=c
    end 
}