perl - 堆中的二级顺序::简单

Question

如何在 Perl 中为 Heap::Simple 接口定义二级排序？

Answer 1

文档指出构造函数采用代码引用来定义顺序，因此您可以指定任何您喜欢的排序方法：

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

每次需要比较两个键时，都会调用给定的代码引用： $less = $code_reference->($key1, $key2);

如果 $key1 小于 $key2 这应该返回一个真值，否则返回一个假值。$code_reference 应该暗示一个总订单关系，所以它需要是可传递的。

通过“二级排序”，我假设您的意思是如果第一个比较显示值相等，则使用第二个比较。假设第一个比较是通过“method1”方法找到的值，第二个比较是来自“method2”的值。因此，如果方法 1 的值不同，则返回该结果，否则回退到方法 2：

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).

Answer 2

首先，您编写一个函数，该函数接受两个要放入堆中的对象，如果第一个小于第二个，则返回 true 值，否则返回 false。

然后将其作为代码引用提供给 Heap::Simple。

Heap::Simple 文档中的示例如下：

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