txt: ## dist_zef-dumarchie-BinaryHeap.md
  # NAME
  
  BinaryHeap - Array-based binary heap supporting heapsort
  
  # SYNOPSIS
  
  ```
  use BinaryHeap;
  
  my BinaryHeap::MinHeap $heap;
  $heap.push(42, 11);
  say $heap.pop; # OUTPUT: «11␤»
  say $heap.top; # OUTPUT: «42␤»
  
  ```
  
  # DESCRIPTION
  
  ```
  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](#method_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␤»
  
  ```
  
  # EXPORTS
  
  ## infix eqv
  
  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](#method_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␤»
  
  ```
  
  ## sub heapsort
  
  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](https://en.wikipedia.org/wiki/Sorting_algorithm#Stability).
  
  # METHODS
  
  ## method Bool
  
  Defined as:
  
  ```
  method Bool( --> Bool:D)
  
  ```
  
  Returns `True` if the heap contains at least one node, and `False` if the heap is empty.
  
  ## method clone
  
  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.
  
  ## method consume
  
  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*.
  
  ## method heapify
  
  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.
  
  ## method new
  
  Defined as:
  
  ```
  method new(+values --> BinaryHeap:D)
  
  ```
  
  Constructs a new heap storing the provided values.
  
  ## method pop
  
  Defined as:
  
  ```
  method pop()
  
  ```
  
  Removes the value stored at the [top](#method_top) of the heap and returns it, or returns a `Failure` if the heap is empty.
  
  ## method push
  
  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␤»
  
  ```
  
  ## method push-pop
  
  Defined as:
  
  ```
  method push-pop(Mu \value)
  
  ```
  
  Functionally equivalent, but more efficient than a [push](#method_push) followed by a [pop](#method_pop). [Replaces the top](#method_replace) of the heap if it `precedes` the provided value; otherwise just returns the provided value.
  
  ## method replace
  
  Defined as:
  
  ```
  method replace(Mu \new)
  
  ```
  
  Functionally equivalent, but more efficient than a [pop](#method_pop) followed by a [push](#method_push). Removes the [top](#method_top) of the heap and returns it after inserting the new value.
  
  ## method sort
  
  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.
  
  ## method top
  
  Defined as:
  
  ```
  method top()
  
  ```
  
  Returns the value stored at the top of the heap, or `Nil` if the heap is empty.
  
  ## method values
  
  Defined as:
  
  ```
  method values( --> Seq:D)
  
  ```
  
  Returns a `Seq` of the values encountered during a breadth-first traversal of the heap.
  
  # SEE ALSO
  
  * [Binary heap - Wikipedia](https://en.wikipedia.org/wiki/Binary_heap)
  * [Heapsort - Wikipedia](https://en.wikipedia.org/wiki/Heapsort)
  * [Raku's built-in `sort` routine](https://docs.raku.org/routine/sort), which is faster than a [`heapsort`](#sub_heapsort) on Rakudo.
  
  # AUTHOR
  
  Peter du Marchie van Voorthuysen
  
  Source can be located at: <https://github.com/dumarchie/raku-binaryheap>
  
  # COPYRIGHT AND LICENSE
  
  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.
  