NAME

Array::Heap::PriorityQueue::Compare - Priority queue with custom comparison

SYNOPSIS

use Array::Heap::PriorityQueue::Compare;
my $pq = Array::Heap::PriorityQueue::Compare->new(sub { $b cmp $a });
$pq->add('banana');
$pq->add('fish');
print $pq->get(), "\n"; # fish
print $pq->peek(), "\n"; # banana

DESCRIPTION

This module implements a priority queue, which is a data structure that can efficiently locate the item with the lowest weight at any time. This is useful for writing cost-minimizing and shortest-path algorithms.

When creating a new queue, you supply a comparison function that is used to order the items.

This module is a wrapper around the *_heap_cmp methods provided by Array::Heap.

FUNCTIONS

Array::Heap::PriorityQueue::Compare->new(\&compare)

Array::Heap::PriorityQueue::Compare->new(sub { ... })

Create a new, empty priority queue. Requires a reference to a comparison function. The example above sorts items in reverse alphabetical order. If your items are hashes containing a weight key, use this:

sub { $a->{weight} <=> $b->{weight} }

If you are storing objects that have their own comparison function:

sub { $a->cmp($b) }

If the order of the objects changes after they are added to the queue, you will need to call restore_order to repair the queue data structure.

$pq->add($item)

Add an item to the priority queue.

$pq->peek()

Return the first (lowest weight) item from the queue. Does not modify the queue. Returns undef if the queue is empty.

$pq->get()

Removes the first item from the priority queue and returns it. Returns undef if the queue is empty.

If two items in the queue have equal weight, this module makes no guarantee as to which one will be returned first. If this is a problem for you, record the order that elements are added to the queue and use that to break ties.

my $pq = Array::Heap::PriorityQueue::Compare->new(sub {
   $a->{weight} <=> $b->{weight} || $a->{order} <=> $b->{order} });
my $order = 0;
foreach my $item (@items) {
   $item->{order} = ++$order;
   $pq->add_unordered($item);
}
$pq->restore_order();

$pq->size()

Returns the number of items in the priority queue.

$pq->items()

Returns all items in the heap, in an arbitrary order.

$pq->sorted_items()

Returns all items in the heap, in weight order.

$pq->add_unordered($item)

Add an item to the priority queue without updating the heap structure. If you are adding a bunch of items at once, it may be more efficient to use add_unordered, then call $pq->restore_order() once you are done.

$pq->restore_order()

Restore the heap structure after calling add_unordered. You need to do this before calling any of the ordered methods (add, peek, or get).

SEE ALSO

Array::Heap::ModifiablePriorityQueue

AUTHOR

Bob Mathews <bobmathews@alumni.calpoly.edu>

REPOSITORY

https://github.com/bobmath/ModifiablePriorityQueue

COPYRIGHT

This program is free software; you can redistribute it and/or modify it under the same terms as Perl itself.

The full text of the license can be found in the LICENSE file included with this module.