Class | PQueue
In: | lib/facets/more/pqueue.rb
Parent: | Object

# 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

gt | [R] | compare Proc
size | [R] | 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).

### Public Instance methods

<<(v)

Alias for push

==(other)

Return true if the queues contain equal elements.

clear()

Remove all elements from the priority queue.

each_pop( {|popped| ...}

Iterate over the ordered elements, destructively.

empty?()

True if there is no more elements left in the priority queue.

include?(element)

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

inspect()

Pretty print

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.

pop_array(n=@size)

Return top n-element as a sorted array.

push(v)

Add an element in the priority queue.

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

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.

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.

replace_top(v)

Replace the top element with the given one, and return this top element.

Equivalent to successively calling pop and push(v).

sort()

Alias for to_a

to_a()

Return a sorted array, with highest priority first.

top()

Return the element with the highest priority.

[Validate]