gistfile1.rb

# BinaryHeap and PriorityQueue based on my Objective-C version

class JBBBinaryHeap
    def initialize(isMaxHeap = false)
        @mStorage = []
        @mCompareProc = (isMaxHeap) ? lambda { |x, y| x < y } : lambda { |x, y| x > y }
    end

    def add(objectToAdd)
        @mStorage.push(nil)
        lastIndex = @mStorage.length - 1
        while (lastIndex > 0)
            parent = (lastIndex - 1) / 2
            parentNode = @mStorage[parent]
            break if (@mCompareProc.call(objectToAdd, parentNode))
            @mStorage[lastIndex] = parentNode
            lastIndex = parent
        end
        @mStorage[lastIndex] = objectToAdd
    end

    def remove
        returnNode = @mStorage[0]
        lastNode = @mStorage.pop
        shiftDown(0, lastNode)
        return returnNode
    end

    def min
        return @mStorage[0]
    end

    def shiftDown(index, objectToShift)
        return if @mStorage.empty?

        while (index < (@mStorage.size / 2))
            child = (2 * index) + 1
        
            child += 1 if ((child < (@mStorage.size - 1)) and @mCompareProc.call(@mStorage[child], @mStorage[child + 1]))

            break unless (@mCompareProc.call(objectToShift, @mStorage[child]))

            @mStorage[index] = @mStorage[child]
            index = child
        end
        @mStorage[index] = objectToShift
    end

    def size
        return @mStorage.size
    end
    alias length size

    def empty?
        return @mStorage.empty?
    end

    def to_s
        return @mStorage.to_s
    end
end

class JBBPQueue
    def initialize(isMaxQueue = false)
        @mObjs = JBBBinaryHeap.new(isMaxQueue)
        @mObjsArray = []
        @mHeapified = false
    end

    def buildHeap
        return if (@mHeapified)

        @mObjsArray.each { |item| @mObjs.add(item) }
        @mObjsArray.clear
        @mHeapified = true
    end

    def push(objectToAdd)
        if (@mHeapified)
            @mObjs.add(objectToAdd)
        else
            @mObjsArray.push(objectToAdd)
        end
    end

    def pushObjects(objectsToAdd = [])
        @mHeapified = false

        @mObjsArray += objectsToAdd
    end

    def pop
        return nil if empty?

        buildHeap

        return @mObjs.remove
    end

    def size
        return @mObjs.size + @mObjsArray.size
    end

    def empty?
        return (size == 0)
    end

    def to_s
        buildHeap

        return @mObjs.to_s
    end
end