class PQueue

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.

Note that as of version 2.0 the internal queue is kept in the reverse order from how it was kept in previous version. If you had used to_a in the past then be sure to adjust for the priorities to be ordered back-to-front instead of the oterh way around.

Constants

VERSION

Attributes

cmp[R]

Priority comparison procedure.

Public Class Methods

new(elements=nil) { |a, b| ... } click to toggle source

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. The block must must take two arguments and return `1`, `0`, or `-1` or `true`, `nil` or `false. It should return `0` or `nil` if the two arguments are considered equal, return `1` or `true` if the first argument is considered greater than the later, and `-1` or `false` if the later is considred to be greater than the first.

By default, the priority queue retrieves maximum elements first using the #<=> method.

# File lib/pqueue.rb, line 39
def initialize(elements=nil, &block) # :yields: a, b
  @que = []
  @cmp = block || lambda{ |a,b| a <=> b }
  replace(elements) if elements
end

Public Instance Methods

<<(v)

Alias of push.

Alias for: push
==(other) click to toggle source

Return true if the queues contain equal elements.

# File lib/pqueue.rb, line 262
def ==(other)
  size == other.size && to_a == other.to_a
end
bottom() click to toggle source

Returns the element with the lowest priority, but does not remove it from the queue.

# File lib/pqueue.rb, line 144
def bottom
  return nil if empty?
  return @que.first
end
clear() click to toggle source

Remove all elements from the priority queue.

# File lib/pqueue.rb, line 197
def clear
  @que.clear
  self
end
concat(elements) click to toggle source

Add more than one element at the same time. See push.

The elements object must respond to to_a, or be a PQueue itself.

# File lib/pqueue.rb, line 154
def concat(elements)
  if empty?
    if elements.kind_of?(PQueue)
      initialize_copy(elements)
    else
      replace(elements)
    end
  else
    if elements.kind_of?(PQueue)
      @que.concat(elements.que)
      sort!
    else
      @que.concat(elements.to_a)
      sort!
    end
  end
  return self
end
Also aliased as: merge!
deq()

Traditional alias for pop.

Alias for: pop
each_pop() { |popped| ... } click to toggle source

Iterate over the ordered elements, destructively.

# File lib/pqueue.rb, line 245
def each_pop #:yields: popped
  until empty?
    yield pop
  end
  nil
end
empty?() click to toggle source

Returns true if there is no more elements left in the queue.

# File lib/pqueue.rb, line 190
def empty?
  @que.empty?
end
enq(v)

Traditional alias for push.

Alias for: push
include?(element) click to toggle source

Return true if the given object is present in the queue.

# File lib/pqueue.rb, line 228
def include?(element)
  @que.include?(element)
end
inspect() click to toggle source

Pretty inspection string.

# File lib/pqueue.rb, line 255
def inspect
  "<#{self.class}: size=#{size}, top=#{top || "nil"}>"
end
length()

Alias of size.

Alias for: size
merge!(elements)

Alias for concat.

Alias for: concat
peek()

Traditional alias for top.

Alias for: top
pop() click to toggle source

Get the element with the highest priority and remove it from the queue.

The highest priority is determined by the block given at instantiation time.

The deletion time is O(log n), with n is the size of the queue.

Return nil if the queue is empty.

# File lib/pqueue.rb, line 101
def pop
  return nil if empty?
  @que.pop
end
Also aliased as: deq
push(v) click to toggle source

Add an element in the priority queue.

# File lib/pqueue.rb, line 74
def push(v)
  @que << v
  reheap(@que.size-1)
  self
end
Also aliased as: enq, <<
replace(elements) click to toggle source

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/pqueue.rb, line 208
def replace(elements)
  if elements.kind_of?(PQueue)
    initialize_copy(elements)
  else
    @que.replace(elements.to_a)
    sort!
  end
  self
end
shift() click to toggle source

Get the element with the lowest priority and remove it from the queue.

The lowest priority is determined by the block given at instantiation time.

The deletion time is O(log n), with n is the size of the queue.

Return nil if the queue is empty.

# File lib/pqueue.rb, line 121
def shift
  return nil if empty?
  @que.shift
end
size() click to toggle source

Returns the size of the queue.

# File lib/pqueue.rb, line 62
def size
  @que.size
end
Also aliased as: length
swap(v) click to toggle source

Push element onto queue while popping off and returning the next element. This is qquivalent to successively calling pop and push(v).

# File lib/pqueue.rb, line 236
def swap(v)
  r = pop
  push(v)
  r
end
take(n=@size) click to toggle source

Return top n-element as a sorted array.

# File lib/pqueue.rb, line 181
def take(n=@size)
  a = []
  n.times{a.push(pop)}
  a
end
to_a() click to toggle source

Return a sorted array, with highest priority first.

# File lib/pqueue.rb, line 221
def to_a
  @que.dup
end
top() click to toggle source

Returns the element with the highest priority, but does not remove it from the queue.

# File lib/pqueue.rb, line 130
def top
  return nil if empty?
  return @que.last
end
Also aliased as: peek

Private Instance Methods

binary_index(que, target) click to toggle source
# File lib/pqueue.rb, line 320
def binary_index(que, target)
  upper = que.size - 1
  lower = 0

  while(upper >= lower) do
    idx  = lower + (upper - lower) / 2
    comp = @cmp.call(target, que[idx])

    case comp
    when 0, nil
      return idx
    when 1, true
      lower = idx + 1
    when -1, false
      upper = idx - 1
    else
    end
  end
  lower
end
heapify()

Alias of sort!

Alias for: sort!
initialize_copy(other) click to toggle source
# File lib/pqueue.rb, line 271
def initialize_copy(other)
  @cmp  = other.cmp
  @que  = other.que.dup
  sort!
end
reheap(k) click to toggle source

The element at index k will be repositioned to its proper place.

This, of course, assumes the queue is already sorted.

# File lib/pqueue.rb, line 282
def reheap(k)
  return self if size <= 1

  que = @que.dup

  v = que.delete_at(k)
  i = binary_index(que, v)

  que.insert(i, v)

  @que = que

  return self
end
sort!() click to toggle source

Sort the queue in accorance to the given comparison procedure.

# File lib/pqueue.rb, line 300
def sort!
  @que.sort! do |a,b|
    case @cmp.call(a,b)
    when  0, nil   then  0
    when  1, true  then  1
    when -1, false then -1
    else
      warn "bad comparison procedure in #{self.inspect}"
      0
    end
  end
  self
end
Also aliased as: heapify