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:

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 !

I looked at the Wikipedia entries for both Min-max_heap, https://en.wikipedia.org/wiki/Min-max_heap, and Double-ended_priority_queue, https://en.wikipedia.org/wiki/Double-ended_priority_queue. The Min-max_heap article had a link to a ‘pdf’ copy of the footnote 1, ACM paper. The double-ended_priority_queue paper mentioned external sorting as an application of the data structure which was of interest to me as someone who once worked for a company that wrote sorting software.