Class | PQueue |
In: |
lib/more/facets/pqueue.rb
|
Parent: | Object |
Priority queue with array based heap.
A priority queue is like a standard queue, except that each inserted elements is given a certain priority, based on the result of the comparison block given at instantiation time. Also, retrieving an element from the queue will always return the one with the highest priority (see pop and top).
The default is to compare the elements in repect to their #> method. For example, Numeric elements with higher values will have higher priorities.
gt | [R] | compare Proc |
size | [R] | number of elements |
Returns a new priority queue.
If elements are given, build the priority queue with these initial values. The elements object must respond to to_a.
If a block is given, it will be used to determine the priority between the elements.
By default, the priority queue retrieves maximum elements first (using the #> method).
# File lib/more/facets/pqueue.rb, line 62 def initialize(elements=nil, &block) # :yields: a, b @qarray = [nil] @size = 0 @gt = block || lambda {|a,b| a > b} replace(elements) if elements end
Return true if the queues contain equal elements.
# File lib/more/facets/pqueue.rb, line 287 def ==(other) return size == other.size && to_a == other.to_a end
Remove all elements from the priority queue.
# File lib/more/facets/pqueue.rb, line 216 def clear @qarray.replace([nil]) @size = 0 return self end
Iterate over the ordered elements, destructively.
# File lib/more/facets/pqueue.rb, line 271 def each_pop #:yields: popped until empty? yield pop end return nil end
True if there is no more elements left in the priority queue.
# File lib/more/facets/pqueue.rb, line 211 def empty? return @size.zero? end
Return true if the given object is present in the queue.
# File lib/more/facets/pqueue.rb, line 266 def include?(element) return @qarray.include?(element) end
Pretty print
# File lib/more/facets/pqueue.rb, line 279 def inspect "<#{self.class}: size=#{@size}, top=#{top || "nil"}>" end
Return the element with the highest priority and remove it from the queue.
The highest priority is determined by the block given at instanciation time.
The deletion time is O(log n), with n the size of the queue.
Return nil if the queue is empty.
# File lib/more/facets/pqueue.rb, line 161 def pop return nil if empty? res = @qarray[1] @qarray[1] = @qarray[@size] @size -= 1 downheap(1) return res end
Add an element in the priority queue.
The insertion time is O(log n), with n the size of the queue.
# File lib/more/facets/pqueue.rb, line 143 def push(v) @size += 1 @qarray[@size] = v upheap(@size) return self end
Add more than one element at the same time. See push.
The elements object must respond to to_a, or to be a PQueue itself.
# File lib/more/facets/pqueue.rb, line 179 def push_all(elements) if empty? if elements.kind_of?(PQueue) initialize_copy(elements) else replace(elements) end else if elements.kind_of?(PQueue) @qarray[@size + 1, elements.size] = elements.qarray[1..-1] elements.size.times{ @size += 1; upheap(@size)} else ary = elements.to_a @qarray[@size + 1, ary.size] = ary ary.size.times{ @size += 1; upheap(@size)} end end return self end
Replace the content of the heap by the new elements.
The elements object must respond to to_a, or to be a PQueue itself.
# File lib/more/facets/pqueue.rb, line 225 def replace(elements) if elements.kind_of?(PQueue) initialize_copy(elements) else @qarray.replace([nil] + elements.to_a) @size = @qarray.size - 1 heapify end return self end
Replace the top element with the given one, and return this top element.
Equivalent to successively calling pop and push(v).
# File lib/more/facets/pqueue.rb, line 251 def replace_top(v) # replace top element if empty? @qarray[1] = v @size += 1 return nil else res = @qarray[1] @qarray[1] = v downheap(1) return res end end