Day 10 — Let’s learn and try double-ended priority queue with Perl 6

Hello! My name is Itsuki Toyota. I’m a web developer in Japan.

In this post, let me introduce Algorithm::MinMaxHeap.

Introduction

Algorithm::MinMaxHeap is a Perl 6 implementation of double-ended priority queue (i.e. min-max heap).¹

Fig.1 shows an example of this data structure:

Fig.1

This data structure has an interesting property, that is, it has both max-heap and min-heap in a single tree.

More precisely, the min-max ordering is maintained in a single tree as the below description:

• values stored at nodes on even levels (i.e. min levels) are smaller than or equal to the values stored at their descendants (if any)
• values stored at nodes on odd levels (i.e. max levels) are greater than or equal to the values stored at their descendants (if any)

Algorithm::MinMaxHeap Internals

I’ll shortly explain what this double-ended priority queue does internally when some frequently used methods (e.g. insert, pop) are called on.²
They maintain the min-max ordering by the following operations:

insert($item)

1. Pushes the given item at the first available leaf position.
2. Checks whether it maintains the min-max ordering by traversing the nodes from the leaf to the root. If it finds a violating node, it swaps this node with a proper node and continues the checking operation.

pop-max

1. Extracts the maximum value node.
2. Fills the vacant position with the last node of the queue.
3. Checks whether it maintains the min-max ordering by traversing the nodes from the filled position to the leaf. If it finds a violating node, it swaps this node with a proper node and continues the checking operation.

pop-min

1. Extracts the minimum value node.
2. Fills the vacant position with the last node of the queue.
3. Checks whether it maintains the min-max ordering by traversing the nodes from the filled position to the leaf. If it finds a violating node, it swaps this node with a proper node and continues the checking operation.

Let’s try !

Then let me illustrate how to use Algorithm::MinMaxHeap.

Example 1

The first example is the simplest one.

Source:

use Algorithm::MinMaxHeap;

my $queue = Algorithm::MinMaxHeap[Int].new; # (#1)
my Int @items = (^10).pick(*);
@items.say; # [1 2 6 4 5 9 0 3 7 8]
$queue.insert($_) for @items; # (#2)
$queue.pop-max.say; # 9 (#3)

In this example, Algorithm::MinMaxHeap[Int].new creates a queue object, where all of its nodes are type Int. (#1)

$queue.insert($_) for @items inserts the numbers in the list. (#2)

$queue.pop-max pops a node which stores the maximum value. (#3)

Example 2

The second example defines user-defined type constraints using subset:

Source (chimera.p6):

use Algorithm::MinMaxHeap;

my subset ChimeraRat of Cool where Num|Rat; # (#1)
my $queue = Algorithm::MinMaxHeap[ChimeraRat].new;

$queue.insert(10e0); # ok
$queue.insert(1/10); # ok
$queue.insert(10); # die # (#2)

Output:

$ perl6 chimera.p6
Type check failed in assignment to @!nodes; expected ChimeraRat but got Int (10)
in method insert at /home/itoyota/.rakudobrew/moar-nom/install/share/perl6/site/sources/240192C19BBAACD01AB9686EE53F67BC530F8545 (Algorithm::MinMaxHeap) line 12
in block  at chimera.p6 line 8

In this example, subset ChimeraRat is a Cool, but only allows Num or Rat. (#1)

Therefore, when you insert 10 to the queue, it returns the error message and die.

It’s because 10 is a Int object. (#2)

Example 3

The third example inserts user-defined classes to the queue.

Source (class.p6):

use Algorithm::MinMaxHeap;

my class State {
 also does Algorithm::MinMaxHeap::Comparable[State]; # (#1) 
 has DateTime $.time;
 has $.payload;
 submethod BUILD(:$!time, :$!payload) { }
 method compare-to(State $s) { # (#2) 
   if $!time == $s.time {
     return Order::Same;
   }
   if $!time > $s.time {
     return Order::More;
   }
   if $!time < $s.time {
     return Order::Less;
   }
 }
}

my @items;

@items.push(State.new(time => DateTime.new(:year(1900), :month(6)),
 payload => "Rola"));
@items.push(State.new(time => DateTime.new(:year(-300), :month(3)),
 payload => "Taro"));
@items.push(State.new(time => DateTime.new(:year(1963), :month(12)),
 payload => "Hanako"));
@items.push(State.new(time => DateTime.new(:year(2020), :month(6)),
 payload => "Jack"));

my Algorithm::MinMaxHeap[Algorithm::MinMaxHeap::Comparable] $queue .= new;
$queue.insert($_) for @items;
$queue.pop-max.say until $queue.is-empty;

Output:

 $ perl6 class.p6
 State.new(time => DateTime.new(2020,6,1,0,0,0), payload => "Jack")
 State.new(time => DateTime.new(1963,12,1,0,0,0), payload => "Hanako")
 State.new(time => DateTime.new(1900,6,1,0,0,0), payload => "Rola")
 State.new(time => DateTime.new(-300,3,1,0,0,0), payload => "Taro")

In this example, the class State does the role Algorithm::MinMaxHeap::Comparable[State], where Algorithm::MinMaxHeap::Comparable[State] defines the stub method compare-to as:
method compare-to(State) returns Order:D { ... };
(#1)

Therefore, in this case, the State class must define a method compare-to so that it accepts a State object and returns an Order:D object. (#2)

Footnote

• ¹ Atkinson, Michael D., et al. “Min-max heaps and generalized priority queues.” Communications of the ACM 29.10 (1986): 996-1000.
• ² For more exact information, please read the above paper.

Thank you for reading my post !