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"; # fishDESCRIPTION
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->weight($item)
-
Returns the weight of the item, or undef if it is not present.
- $pq->min_weight($item)
-
Returns the minimum weight from the queue, or undef if empty.
- $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, $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 and weight functions run in constant time, or O(1) in asymptotic notation. The structure-modifying functions add, get, and remove run in O(log n) time. The items function is O(n), and sorted_items is O(n log n). 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 don't need the modifiable features of this module, consider using Array::Heap::PriorityQueue::Numeric instead.
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.
SEE ALSO
Heap for a different priority queue implementation.
Heap::Simple is easy to use, but doesn't allow weights to be changed.
Array::Heap if you need more direct access to the data structure.
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.