数组：：使用自定义比较函数的堆

Question

我正在试验Array::Heap模块，并希望创建一个按反向顺序排序的堆。所以我创建了这个代码：

#!/usr/bin/perl

use utf8;
use strict;
use warnings;
use Array::Heap;

my @heap;
make_heap_cmp {$b <=> $a} @heap;
push_heap_cmp {$b <=> $a} @heap, 4;
push_heap_cmp {$b <=> $a} @heap, 1;
push_heap_cmp {$b <=> $a} @heap, 5;
push_heap_cmp {$b <=> $a} @heap, 7;
push_heap_cmp {$b <=> $a} @heap, 2;

while (my $val = pop_heap_cmp {$b <=> $a} @heap)
{
    print "$val\n";
}

是正确的，它输出7，5，4，2，1。

但是代码看起来很难看:我对每个调用都重复了比较函数。不幸的是，模块文档缺乏用于特殊比较功能的用例示例。有人能告诉我，是否有可能改进这段代码或建议一个更好的模块，实现堆吗？

Answer 1

这就是潜艇的用途。

my $rev = sub { $b <=> $a };

sub make_heap_rev(\@)  { &make_heap_cmp($rev, @_) }
sub push_heap_rev(\@@) { &push_heap_cmp($rev, @_) }
sub pop_heap_rev(\@)   { &pop_heap_cmp($rev, @_) }

然后你可以用

my @heap = ( 4, 1, 5, 7, 2 );
make_heap_rev @heap;
while (my $val = pop_heap_rev @heap) {
   say $val;
}

或

my @heap;
push_heap_rev @heap, 4, 1, 5, 7, 2;
while (my $val = pop_heap_rev @heap) {
   say $val;
}

Answer 2

将代码放在一个循环中：

my @heap;

for my $i (4, 1, 5, 7, 2) {
  push_heap_cmp {$b <=> $a} @heap, $i;
}

或者将复杂性隐藏在子程序中；

sub add_to_heap {
   my ($heap, $add) = @_;

   push_heap_cmp { $b <=> $a } @$heap, $add;
}

my @heap;

for my $i (4, 1, 5, 7, 2) {
  add_to_heap \@head, $i;
}