Вторичный порядок в куче :: Простой

Question

Как определить вторичный порядок в интерфейсе Heap :: Simple в Perl?

Answer 1

В документации говорится, что конструктор использует ссылку на код для определения порядка, поэтому вы можете указать любой метод сортировки, который вам нравится:

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

Каждый раз, когда два ключанеобходимо сравнить, данная ссылка на код будет называться следующим образом: $ less = $ code_reference -> ($ key1, $ key2);

Это должно вернуть истинное значение, если $ key1 меньше, чем $ key2 иложное значение в противном случае.$ code_reference должно подразумевать отношение общего порядка, поэтому оно должно быть транзитивным.

Под "вторичным порядком" я предполагаю, что вы имеете в виду, что используется второе сравнение, если первое показывает, что значения равны,Допустим, первое сравнение имеет значения, найденные с помощью метода «method1», а второе сравнение - значения из «method2».Таким образом, если для method1 значения отличаются, возвращают этот результат и в противном случае возвращаются к method2:

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

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

    return 1 if $result == -1;
}

Если method1 и method2 возвращают строки вместо числовых значений, просто используйте оператор cmp вместо<=>.Вы можете использовать все что угодно, если оператор возвращает правильные значения.Большинство функций сортировки, например, используют значения -1, 0 и 1, чтобы указать, меньше ли значение1, равно или больше, чем значение2, но этот модуль предпочитает, чтобы значение 1 означало val1

Answer 2

Прежде всего, вы пишете функцию, которая принимает два объекта, которые вы хотите поместить в кучу, и возвращает истинное значение, если первый меньше второго, и ложное в противном случае.

Затем укажите это как coderef для 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