NAME

Array::Heap::ModifiablePriorityQueue - Modifiable priority queue

SYNOPSIS

use Array::Heap::ModifiablePriorityQueue;
my $pq = Array::Heap::ModifiablePriorityQueue->new();
$pq->add('fish', 42);
$pq->add('banana', 27);
print $pq->peek(), "\n"; # banana
$pq->remove('banana');
print $pq->get(), "\n"; # fish

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.

Why another priority queue module? First, unlike many similar modules, this one allows you to modify the queue. Items can be removed from the queue or have their weight changed after they are added.

Second, it simple to use. Items in the queue don't have to implement any specific interface. Just throw them in there along with a weight value and the module will keep track of everything.

Finally, it has good performance on large datasets. This is because it is based on a partially-ordered heap data structure. Many other priority queue modules are based on fully sorted lists (even ones that claim to be heaps). Keeping the items only partially sorted saves time when there are are a large number of them (several thousand or so).

This module is a Perl wrapper around Array::Heap, a lightweight and fast heap management module implemented in XS.

FUNCTIONS

Array::Heap::ModifiablePriorityQueue->new()

Create a new, empty priority queue.

$pq->add($item, $weight)

Add an item to the priority queue with the given weight. If the item is already present in the queue, modify its weight. Weight must be numeric.

$pq->peek()

Return the first (numerically 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.

$pq->remove($item)

Removes the given item from the priority queue. If item is not present in the queue, does nothing.

$pq->size()

Returns the number of items in the priority queue.

$pq->add_unordered($item, $weight)

Add an item to the priority queue or change its weight, 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->remove_unordered($item)

Remove an item from the priority queue without updating the heap structure. If item is not present in the queue, do nothing.

$pq->restore_order()

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

PERFORMANCE

The peek function runs in constant time, or O(1) in asymptotic notation. The structure-modifying functions add, get, and remove run in O(log n) time. Add_unordered and remove_unordered are O(1), but after a sequence of unordered operations, you need to call restore_order, which is O(n).

If you feel that you need maximum speed, go ahead and inline these methods into your own code to avoid an extra method invocation. They are all quite short and simple.

LIMITATIONS

• Weight values must be numeric. This is a limitation of the underlying Array::Heap module.

• Weights are sorted in increasing order only. If you want it the other way, use the negative of the weights you have.

• Items are distinguished by their stringified values. This works fine if you are storing scalars or plain references. If your items have a custom stringifier that returns nonunique strings, or their stringified value can change, you may need to use Array::Heap directly.

AUTHOR

Bob Mathews <bobmathews@alumni.calpoly.edu>

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.