Help language development. Donate to The Perl Foundation

e646d7b7481f97c7a5bb87ece0ee55244cfca410/

BinaryHeap - Array-based binary heap supporting heapsort

```raku use BinaryHeap;

my BinaryHeap::MinHeap $heap; $heap.push(42, 11); say $heap.pop; # OUTPUT: «11» say $heap.top; # OUTPUT: «42» ```

```
role BinaryHeap[&infix:<precedes> = * cmp * == Less] {}
```

Role `BinaryHeap`

stores values in an implicit binary tree that satisfies the **heap property**: the value of a node never `precedes`

the value of its parent node.

Infix `precedes`

defines a priority relation, such that the root of the tree, known as the top of the heap, has a priority higher than or equal to all other nodes of the tree. The default relation defines a *min-heap*, i.e. the top value compares `Less`

than or `Same`

as every other value on the heap.

Module `BinaryHeap`

provides two classes that mix in the role:

`class BinaryHeap::MaxHeap does BinaryHeap[* cmp * == More]`

In a

*max-heap*, a child node never compares`More`

than its parent node.`class BinaryHeap::MinHeap does BinaryHeap[* cmp * == Less]`

In a

*min-heap*, a child node never compares`Less`

than its parent node.

These classes are parameterizable with a custom three-way comparison operator. For example, this *max-heap* compares objects by their `.key`

:

```
my BinaryHeap::MaxHeap[*.key cmp *.key] $heap;
```

An uninitialized `BinaryHeap`

is a valid representation of an empty heap. This means that all documented methods can be called on a type object. Methods that may add values to the heap try to autovivify an uninitialized invocant, which means they can only be called on a *container* that stores or defaults to a *class* type. For example, given the uninitialized `$heap`

declared above:

```
say $heap.values; # OUTPUT: «()»
say $heap.replace(42); # OUTPUT: «Nil»
say $heap.top; # OUTPUT: «42»
```

Defined as:

```
multi sub infix:<eqv>(BinaryHeap \a, BinaryHeap \b --> Bool:D)
```

Returns `True`

if and only if the two heaps are of the same type and contain equivalent values. Note that a concrete heap is of a different type than a role, so:

```
say BinaryHeap.new eqv BinaryHeap; # OUTPUT: «False»
say BinaryHeap::MaxHeap.new eqv BinaryHeap::MaxHeap; # OUTPUT: «True»
```

Defined as:

```
multi sub heapsort(@array, :$reverse)
multi sub heapsort(&comparator, @array, :$reverse)
```

Sorts and returns the `@array`

, using a custom three-way `&comparator`

if provided. By default the array is sorted in ascending order, but it is sorted in descending order if `:$reverse`

is true. Hence, the following statements both put the elements of the array in descending order:

```
heapsort @array, :reverse;
heapsort -(* cmp *), @array;
```

Note that `heapsort`

is not a stable sort.

Defined as:

```
method Bool( --> Bool:D)
```

Returns `True`

if the heap contains at least one node, and `False`

if the heap is empty.

Defined as:

```
multi method clone(BinaryHeap:D: --> BinaryHeap:D)
```

Returns a clone of the invocant. The clone is based on a distinct array, so modifications to one heap will not affect the other heap.

Defined as:

```
method consume( --> Seq:D)
```

Returns a `Seq`

that generates values by removing them from the top of the heap. If no values are inserted into the heap before the `Seq`

is exhausted, the values will be in ascending order if called on a *min-heap*, in descending order if called on a *max-heap*.

Defined as:

```
method heapify(@array --> BinaryHeap:D)
```

Constructs a new heap based on the provided array, whose elements are put in heap order. The `@array`

should not be modified directly while the heap is in use.

Defined as:

```
method new(+values --> BinaryHeap:D)
```

Constructs a new heap storing the provided values.

Defined as:

```
method pop()
```

Removes the value stored at the top of the heap and returns it, or returns a `Failure`

if the heap is empty.

Defined as:

```
method push(**@values --> BinaryHeap:D)
```

Inserts the provided values into the heap and returns the modified heap. Autovivifies the invocant if called on a container storing or defaulting to a class type object. For example:

```
my BinaryHeap::MaxHeap $heap;
$heap.push(42, 11);
say $heap.pop; # OUTPUT: «42»
say $heap.top; # OUTPUT: «11»
```

Defined as:

```
method push-pop(Mu \value)
```

Functionally equivalent, but more efficient than a push followed by a pop. Replaces the top of the heap if it `precedes`

the provided value; otherwise just returns the provided value.

Defined as:

```
method replace(Mu \new)
```

Functionally equivalent, but more efficient than a pop followed by a push. Removes the top of the heap and returns it after inserting the new value.

Defined as:

```
method sort()
```

Returns an empty `Array`

if called on an uninitialized heap. Otherwise sorts the underlying array in descending order if called on a *min-heap*, in ascending order if called on a *max-heap*. Replaces the underlying array with an empty copy and returns the sorted array.

Defined as:

```
method top()
```

Returns the value stored at the top of the heap, or `Nil`

if the heap is empty.

Defined as:

```
method values( --> Seq:D)
```

Returns a `Seq`

of the values encountered during a breadth-first traversal of the heap.

Raku's built-in

`sort`

routine, which is faster than a`heapsort`

on Rakudo.

Peter du Marchie van Voorthuysen

Source can be located at: https://github.com/dumarchie/raku-binaryheap

Copyright 2022 Peter du Marchie van Voorthuysen

This library is free software; you can redistribute it and/or modify it under the Artistic License 2.0.