Secondary Order in Heap::Simple

Question

How do I define a secondary ordering to the Heap::Simple interface in Perl?

Answer 1

First of all, you write a function that takes two of the objects you want to put in the heap, and returns a true value if the first one is smaller than the second, and false otherwise.

Then supply that as a coderef to Heap::Simple.

The example from the Heap::Simple docs is as follows:

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

Answer 2

The documentation states that the constructor takes a code reference to define the order, so you can specify any sort method you like:

my $heap = Heap::Simple->new(order => \&sort_method);

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. $code_reference should imply a total order relation, so it needs to be transitive.

By "secondary ordering" I assume you mean that a second comparison is used if the first one shows the values to be equal. Let's say the first comparison is of values found via the "method1" method, and the second comparison is of values from "method2". So, if by method1 the values are different, return that result, and otherwise fall back to method2:

sub sort_method
{
    my ($val1, $val2) = @_;

    my $result = ($val1->method1 <=> $val2->method1)
                          ||
                 ($val1->method2 <=> $val2->method2);

    return 1 if $result == -1;
}

If method1 and method2 return strings instead of numeric values, simply use the cmp operator instead of <=>. You can use anything you like, as long as the operator returns the right values. Most sort functions like using the values -1, 0 and 1 to indicate whether value1 is less than, equal to, or greater than value2, but this module likes 1 to mean val1 < val2, so after gathering the -1, 0, 1 result, one then returns 1 if the result is -1 (where value1 is less than value2).