Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- # 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
Add Comment
Please, Sign In to add comment