|
Heap::Simple - Fast and easy to use classic heaps |
Heap::Simple - Fast and easy to use classic heaps
use Heap::Simple;
# Create a heap
my $heap = Heap::Simple->new;
my $heap = Heap::Simple->new(%options);
# Put data in the heap
$heap->insert(@new_elements);
# Put data in a "Object" or "Any" heap with a given key
$heap->key_insert($key1, $element1, $key2, $element2, ...);
# Extract the top value
$element = $heap->extract_top; # croaks on an empty heap
$element = $heap->extract_first; # returns undef on an empty heap
# Get the top value but leave it in the heap
$element = $heap->top; # croaks on an empty heap
$element = $heap->first; # returns undef on an empty heap
# Find the top key in the heap
$top_key = $heap->top_key; # return infinity on an empty heap
# croaks if there's no infinity
$top_key = $heap->first_key; # returns undef on an empty heap
# Ordered extract of all data whose key is not above a given value
@elements = $heap->extract_upto($max_key);
# Ordered extract of all data
@elements = $heap->extract_all;
# Empty the heap
$heap->clear;
# Find the number of elements
$count = $heap->count;
# Get all keys (not sorted)
@keys = $heap->keys;
# Get all values (not sorted)
@values = $heap->values;
# Find the key corresponding to a value
$key = $heap->key($value);
# Get/Set user_data
$user_data = $heap->user_data;
$old_data = $heap->user_data($new_data);
# Get/Set infinity
$infinity = $heap->infinity;
$old_infinity = $heap->infinity($new_data);
# Get the position of a key in an element
$key_index = $heap->key_index;
$key_name = $heap->key_name;
$key_method = $heap->key_method;
$key_function = $heap->key_function;
# Return the value of several things that were set in new:
$wrapped = $heap->wrapped;
$max_count = $heap->max_count;
$can_die = $heap->can_die;
$dirty = $heap->dirty;
$order = $heap->order;
@elements = $heap->elements;
$elements = $heap->elements;
# Move all elements out of each heap in @heaps and into $heap
$heap->absorb(@heaps); # As if doing a repeated $heap->insert
$heap->key_absorb(@heaps); # As if doing a repeated $heap->key_insert
# merge already sorted arrays into a new sorted array
# This doesn't disturb the elements already in the heap
my $merged_aref = $heap->merge_arrays($aref1, $aref2, ...);
# Which class does the actual work ?
$implementation = Heap::Simple->implementation;
When key and value are kept separate:
use Heap::Simple;
my $heap = Heap::Simple->new(elements => "Any");
$heap->key_insert(8, "bar");
$heap->key_insert(5, "foo");
# This will print foo (5 is the top key)
print "First value is ", $heap->extract_top, "\n";
$heap->key_insert(7, "baz");
# This will print baz (7 is the top key)
print "Next value is ", $heap->extract_top, "\n";
# This will print bar (8 is now the top key)
print "Next value is ", $heap->extract_top, "\n";
When the key is part of the value:
# This is purely for display, ignore it
use Data::Dumper;
$Data::Dumper::Indent = 0;
$Data::Dumper::Terse = 1;
# Real code starts here
use Heap::Simple;
my $heap = Heap::Simple->new(elements => "Array");
$heap->insert([8, "bar"]);
$heap->insert([5, "foo"]);
# This will print [5, foo] (5 is the top key)
print "First value is ", Dumper($heap->extract_top), "\n";
$heap->insert([7, "baz"]);
# This will print [7, baz] (7 is the top key)
print "Next value is ", Dumper($heap->extract_top), "\n";
# This will print [8, bar] (8 is now the top key)
print "Next value is ", Dumper($heap->extract_top), "\n";
A heap is a partially sorted structure where it's always easy to extract the smallest element. If the collection of elements is changing dynamically, a heap has less overhead than keeping the collection fully sorted.
The order in which equal elements get extracted is unspecified.
The main order relations supported by this module are ``<'' (numeric compare) and ``lt'' (string compare).
The module allows you to manage data where the elements are of several allowed types, in particular array references, hash references, objects or just the keys themselves.
So new has a lot of ways to specify element types, but the right choices follows quite directly from the data you'll put in the heap. If the key is part of the data (or easily derived from the data), choose an element type that tells how to get the key out of the data, and insert elements using insert. If the key is independent from the data or you want to avoid repeated key calculations, use the Any element type and insert elements using key_insert.
The internals of the module do nothing with the elements inserted except inspecting the key. This means that if you for example store a blessed object, that's what you will get back on extract. It's also ok to keep references to the elements around and make changes to them while they are in the heap as long as you don't change the key.
Heap::Simple itself is just a loader for the code that will actually implement the functionality mentioned above. You will need to install something like Heap::Simple::XS or Heap::Simple::Perl to be able to actually do anything.
None.
All methods that can fail will thrown an exception in case of failure unless otherwise specified. For example, you don't have to explicitely check the result of new, it will already thrown an exception in case of bad arguments.
You could for example use this to print a list of numbers from low to high:
use Heap::Simple;
my $heap = Heap::Simple->new;
$heap->insert(8, 3, 14, -1, 3);
print $heap->extract_top, " " for 1..$heap->count;
print "\n";
# Will print: -1 3 3 8 14
This example is silly of course. You could just as well directly use perl sort. But in real applications you would do the inserting interleaved with extracting and always keeping the list sorted would become inefficient for big lists. That is where you would use a heap. The examples we give will however be like the one above so you can quickly see the way in which the methods are supposed to be called.
For some applications this basic usage where you just store numeric keys will be good enough, but usually you want to be able to store more complex elements.
Several options can help you with that:
my $heap = Heap::Simple->new(order => "<");
and the result would have been exactly the same.
The default infinity for this order is +inf.
Repeating the example with this order gives:
use Heap::Simple;
my $heap = Heap::Simple->new(order => ">");
$heap->insert(8, 3, 14, -1, 3);
print $heap->extract_top, " " for 1..$heap->count;
print "\n";
# Will print: 14 8 3 3 -1
The default infinity for this order is -inf.
use Heap::Simple;
my $heap = Heap::Simple->new(order => "lt");
$heap->insert("ate", 8, 3, "zzzz", 14, -1, 3, "at");
print $heap->extract_top, " " for 1..$heap->count;
print "\n";
# Will print: -1 14 3 3 8 at ate zzzz
Notice how 14 comes before 3 as you would expect in lexical sorting.
The default infinity for this order is ``undef'' (there is no maximum string)
use Heap::Simple;
my $heap = Heap::Simple->new(order => "gt");
$heap->insert("ate", 8, 3, "zzzz", 14, -1, 3, "at");
print $heap->extract_top, " " for 1..$heap->count;
print "\n";
# Will print: zzzz ate at 8 3 3 14 -1
The default infinity for this order is ``'' (the empty string)
Every time two keys need to be compared, the given code reference will be called like:
$less = $code_reference->($key1, $key2);
This should return a true value if $key1 is smaller than $key2 and a false value otherwise (actually, since the order of equal elements is unspecified, it's ok to return true in case of equality too). $code_reference should imply a total order relation, so it needs to be transitive.
Since in this case nothing can be determined about the key type, there will be no infinity by default (even if the keys are numbers).
Example:
use Heap::Simple;
sub more { return $_[0] > $_[1] }
my $heap = Heap::Simple->new(order => \&more);
$heap->insert(8, 3, 14, -1, 3);
print $heap->extract_top, " " for 1..$heap->count;
print "\n";
# Will print: 14 8 3 3 -1
The code reference will be called many times during normal heap operations (O(log n) times for a single insert or extract on a size n heap), so only use this order type within reason. Usually it's better to precalculate some number or string representation of some sort of key and use normal compares on these. You can use the Any element type and key_insert to wrap the precalculated key with the corresponding element, or you can delegate the key calculation to the insert method and use one of the Method, Object or Function element types.
Here's an example of such ``fake'' keys:
# "human" sorting mixed strings
use Heap::Simple;
sub key {
my $str = uc(shift);
$str =~ s|(0*)(\d+)|pack("AN/A*N", "0", $2, length($1))|eg;
return $str;
}
my $heap = Heap::Simple->new(order => "lt",
elements => [Function => \&key]);
$heap->insert(qw(Athens5.gr Athens40.gr
Amsterdam51.nl Amsterdam5.nl amsterdam20.nl));
print $heap->extract_top, "\n" for 1..$heap->count;
# This will print:
Amsterdam5.nl
amsterdam20.nl
Amsterdam51.nl
Athens5.gr
Athens40.gr
The $element_type is usually an array reference, but if the array has only one entry, you may use that directly. So you can use:
elements => "Array"
instead of:
elements => ["Array"]
The following element types are currently supported:
my $heap = Heap::Simple->new(order => "lt",
elements => ["Scalar"]);
or in the simplified notation:
my $heap = Heap::Simple->new(order => "lt", elements => "Scalar");
This element type used to be called Key, and that name is still accepted
for backward compatibility.
use Heap::Simple;
my $heap = Heap::Simple->new(order => "lt",
elements => [Array => 0]);
while (my ($key, $val) = each %hash) {
$heap->insert([$key, $val]);
}
for (1..$heap->count) {
print $heap->extract_top->[1], "\n";
}
You can always use something like [$key, @data] to pair up keys and data, so the ``Array'' element type is rather generally useful (but see the Object and Any element types for another way to pair keys with data). Since it's so common to have the key in the first position, you may in fact drop the index in that case, so the constructor in the previous example could also be written as:
my $heap = Heap::Simple->new(order => "lt",
elements => ["Array"]);
or using the one element rule:
my $heap = Heap::Simple->new(order => "lt",
elements => "Array");
In case the elements you want to store are arrays (or array based objects (or fields based objects) and you are prepared to break the object encapsulation), this element type is also very nice. If for example the value on which you want to order is a number at position 4, you could use:
my $heap = Heap::Simple->new(elements => [Array => 4]);
print "The key is $object->[4]\n";
$heap->insert($object);
Redoing the Array example in Hash style gives:
use Heap::Simple;
my $heap = Heap::Simple->new(order => "lt",
elements => [Hash => "tag"]);
while (my ($key, $val) = each %hash) {
$heap->insert({tag => $key, value => $val});
}
for (1..$heap->count) {
print $heap->extract_top->{value}, "\n";
}
In case the elements you want to store are hashes (or hash based objects and you are prepared to break the object encapsulation), this element type is also very nice. If for example the value on which you want to order is a number with key ``price'', you could use:
my $heap = Heap::Simple->new(elements => [Hash => "price"]);
print "The key is $object->{price}\n";
$heap->insert($object);
The method method_name will be called like:
$key = $element->$method_name();
and should return the key corresponding to $element.
Suppose that the elements are objects whose weight you can access using the ``weight'' method. A heap ordered on weight then becomes:
my $heap = Heap::Simple->new(elements => [Method => "weight"]);
print "The key is ", $object->weight(), "\n";
$heap->insert($object);
So this element type will only call $method_name once on the initial insert, after which internally the key is stored together with the value. This makes it faster, but it also uses more memory.
It also means that it's now perfectly fine to make changes to the object that change the key while it is in the heap. This will have absolutely no influence on the ordering anymore, and methods like first_key will still return what the key value was at insert time.
Repeating the previous example in this style is a trivial variation:
my $heap = Heap::Simple->new(elements => [Object => "weight"]);
print "The key is ", $object->weight(), "\n";
$heap->insert($object);
Since for this element type the key is almost completely decoupled from the value and only fetched on insert, it often makes sense to not let the heap calculate the key, but do it yourself before the insert, and then use key_insert. In fact, if you never use plain insert at all, you don't even have to bother passing a method name (though in that case the fact that the thing you store is an object is pretty irrelevant and it's probable more natural to use the Any element type).
$key = $code_reference->($element);
and should return the key corresponding to $element.
An example:
sub price {
my $items = shift;
my $price = 0;
$price += $_->price for @$items;
return $price;
}
my $heap = Heap::Simple->new(elements => [Function => \&price]);
print "All items together will cost ", $item_list->price, "\n";
$heap->insert($item_list);
So if you are prepared to use more memory, you can again tell Heap::Simple to calculate the key already at insert time, and store it together with the value. This will avoid the need for repeated key calculations.
The ``Any'' element type will do this for you transparantly.
The heap part of the above example becomes:
my $heap = Heap::Simple->new(elements => [Any => \&price]);
print "All items together will cost ", $item_list->price, "\n";
$heap->insert($item_list);
Since for this element type the key is almost completely decoupled from the value and only fetched on insert, it often makes sense to not let the heap calculate the key, but do it yourself before the insert, and then use key_insert. In fact, if you never use plain insert at all, you don't even have to bother passing the code reference. So the last example could look like:
my $heap = Heap::Simple->new(elements => "Any");
my $price = $item_list->price;
print "All items together will cost $price\n";
$heap->key_insert($price, $item_list);
Or we can use it to simplify the hash sort on key example a bit:
use Heap::Simple;
my $heap = Heap::Simple->new(order => "lt",
elements => "Any");
# A hash in list context returns a sequence of key/value pairs
$heap->key_insert(%hash);
for (1..$heap->count) {
print $heap->extract_top, "\n";
}
A max count of 0 may or may not be supported depending on the implementor.
You can for example use this to determine the three highest values in an array:
use Heap::Simple;
my @array = qw(19 3 7 -5 3 18 1);
my $heap = Heap::Simple->new(max_count => 3);
$heap->insert(@array);
print "The three highest values are: ", join(", " => $heap->values), "\n";
# Will print: The three highest values are: 7, 19, 18
If you give a true value to can_die, the code for single element operations will be changed so that they will properly recover by undoing what just got changed (so a failing operation becomes a no-op). This however will slow down these operations somewhat, so the default is actually false (most of the time getting exceptions during the heap operations is impossible anyways).
Operations that insert or extract multiple elements will also get their code changed so the heap is always left in a consistent state, but the operation is not atomic since it could already be executed on some of the elements. You could even lose elements if for example an extract_all fails halfway through (the already extracted part is gone from the heap but you never got a chance to store the methods return values).
Multi element operations can be substantially more efficient without this flag since it may allow the use of better algorithms.
This is a per heap option, so only those heaps that actually set this will see any slowdown.
All operations that don't change the heap (like count or top) are always safe.
Note that all change operations always assume you won't recursively cause another change to the same heap while they are running. If you do that, all bets for consistency are are off, even if you set this option.
The default is no dirty optimizations.
If this option is not given, the heap starts with ``undef'' associated to it.
my $heap = Heap::Simple->new(user_data => "foo");
print $heap->user_data, "\n";
# prints foo
The default value depends on the order relation that was specified.
Usually you can just forget about this option. Only top_key really cares.
Notice that the class into which the resulting heap is blessed will not be Heap::Simple. It will be an on demand generated class that will have Heap::Simple as an ancestor.
insert(@new_elements)In case an exception is raised during insert the heap is only guaranteed to be in a consistent state if you had set the can_die flag to new. Even then it's possible that some first part of @new_elements has been inserted into the heap while the rest hasn't (they get inserted in the order given). You could check how many by calling the count method before and after the insert. So even with can_die only inserts of single elements are atomic.
Mass insert can be substantially faster if the can_die flag isn't set though.
On extraction you get back exactly the same $element as you inserted, including a possible blessing.
In case an exception is raised during insert the heap is only guaranteed to be in a consistent state if you had set the can_die flag to new. Even then it's possible that some first part of the argument list has been inserted into the heap while the rest hasn't (they get inserted in the order given). You could check how many by calling the count method before and after the insert. So even with can_die only inserts of single key/element pairs are atomic.
Mass insert can be substantially faster if the can_die flag isn't set though.
This method used to be called "extract_min" instead of "extract_top".
The old name is still supported but is deprecated.
Throws an exception if the heap is empty.
Throws an exception if the heap is empty.
Since the data returned from a non-empty heap can often not be undef, you could use this method to check if a heap is empty, but it's probably more natural to use count for that.
Example:
use Heap::Simple;
my $heap = Heap::Simple->new;
$heap->insert(8, 3, 14, -1, 3);
print $heap->first, "\n";
# prints -1
Example:
use Heap::Simple;
my $heap = Heap::Simple->new;
$heap->insert(8, 3, 14, -1, 3);
print $heap->first_key, "\n";
# prints -1
Example:
use Heap::Simple;
my $heap = Heap::Simple->new;
$heap->insert(8, 3, 14, -1, 3);
print $heap->top_key, "\n";
# prints -1
This method used to be called ``min_key'' instead of ``top_key''. The old name is still supported but is deprecated.
extract_upto($max_key)Returns an empty list for the empty heap.
Example:
use Heap::Simple;
my $heap = Heap::Simple->new;
$heap->insert(8, 3, 14, -1, 3);
print join(", ", $heap->extract_upto(3)), "\n";
# prints -1, 3, 3
This method will lose values in case of an exception even if can_die is true (remember that exceptions of this type are only possible if you have a self coded key fetch or compare that can die, so this is normally irrelevant).
Example:
use Heap::Simple;
my $heap = Heap::Simple->new;
$heap->insert(8, 3, 14, -1, 3);
print join(", ", $heap->extract_all), "\n";
# prints -1, 3, 3, 8, 14
This method can lose values in case of an exception even if can_die is true (remember that exceptions of this type are only possible if you have a key fetch or compare that can die, so this is normally irrelevant).
If you don't actually care about the order of the elements it's more efficient to use values followed by clear.
It's unspecified what this method returns in scalar context.
use Heap::Simple;
my $heap = Heap::Simple->new;
$heap->insert(8, 3, 14, -1, 3);
print $heap->count, "\n";
# prints 5
This method may imply a lot of function calls if getting the key from an element implies a function call (as it does for the Method and Function element types, but not for the Object and Any element types).
Multiple calls to an unchanged heap will return the keys in the same order, which is also consistent with the order of values
Multiple calls to an unchanged heap will return the values in the same order, which is also consistent with the order of keys
key($value)Notice that this does not access the elements in the heap in any way. In particular, it's not looking for $value in the heap hoping to match its key.
user_data($new_data)infinity($new_infinity)<, >, lt, gt or a code reference).
absorb(@heaps)
for my $work_heap (@heaps) {
$heap->insert(reverse $work_heap->values);
$work_heap->clear;
}
except that it may be more efficient.
If an exception is possible and gets raised during insert, the heaps will be left in a consistent state with a partial transfer completed on the condition that can_die is set for $heap (the settings for the heaps in @heaps are irrelevant, their accesses there will always be done in a safe way)
key_absorb(@heaps)
for my $work_heap (@heaps) {
my @values = $work_heap->values;
my @keys = $work_heap->keys;
$heap->key_insert(pop @keys, pop @values) while @values;
$work_heap->clear;
}
except that it's may be more efficient. This is mainly meant for transfer between wrapped heap types (Any and Object) since it avoids key recalculation. $heap must of course be a wrapped heap type.
If an exception is possible and gets raised during insert, all heaps will be left in a consistent state with a partial transfer completed on the condition that can_die is set for $heap (the setting for the heaps in @heaps are irrelevant, their accesses there will always be done in a safe way)
$merge_aref = [sort { $heap->compare_function->($a, $b) } map @$_, @_;
shift @$merge_aref until @$merge_aref <= $heap->max_count;
except that it's more efficient (e.g. it uses the knowledge that the argument arrays are already sorted).
It leaves values stored in the $heap completely untouched. $heap is only used for its attributes, how to find the key, what the compare function is and the maximum number of elements.
"Heap::Simple::XS" or "Heap::Simple::Perl".
the Heap::Simple::Perl manpage, the Heap::Simple::XS manpage
Some other heap or heap-like classes that exist:
the Heap manpage, the Heap::Priority manpage, the Array::Heap2 manpage
Ton Hospel, <Heap-Simple@ton.iguana.be>
Copyright 2003 by Ton Hospel
This library is free software; you can redistribute it and/or modify it under the same terms as Perl itself.
|
Heap::Simple - Fast and easy to use classic heaps |