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

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

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

Thank you for reading my post !