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.

Methods
<< == clear each_pop empty? include? inspect merge new pop pop_array push push_all replace replace_top sort to_a top
Attributes
[R] gt compare Proc
[R] size number of elements
Public Class methods
new(elements=nil) {|a, b| ...}

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
Public Instance methods
<<(v)

Alias for push

==(other)

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
clear()

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
each_pop( {|popped| ...}

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
empty?()

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
include?(element)

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
inspect()

Pretty print

# File lib/more/facets/pqueue.rb, line 279
  def inspect
    "<#{self.class}: size=#{@size}, top=#{top || "nil"}>"
  end
merge(elements)

Alias for push_all

pop()

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
pop_array(n=@size)

Return top n-element as a sorted array.

# File lib/more/facets/pqueue.rb, line 203
  def pop_array(n=@size)
    ary = []
    n.times{ary.push(pop)}
    return ary
  end
push(v)

Add an element in the priority queue.

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

This method is also aliased as <<
# File lib/more/facets/pqueue.rb, line 143
  def push(v)
    @size += 1
    @qarray[@size] = v
    upheap(@size)
    return self
  end
push_all(elements)

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.

This method is also aliased as merge
# 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(elements)

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_top(v)

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
sort()

Alias for to_a

to_a()

Return a sorted array, with highest priority first.

This method is also aliased as sort
# File lib/more/facets/pqueue.rb, line 237
  def to_a
    old_qarray = @qarray.dup
    old_size = @size
    res = pop_array
    @qarray = old_qarray
    @size = old_size
    return res
  end
top()

Return the element with the highest priority.

# File lib/more/facets/pqueue.rb, line 171
  def top
    return nil if empty?
    return @qarray[1]
  end