Heap¶
Usage
use Heap;
or
import Heap;
This module contains the implementation of a ‘heap’ type.
A heap is a specialized tree-based data structure that supports extracting the maximal or the minimal element quickly, which can serve as a priority queue.
Both push and pop operations are O(lgN).
Querying the top element is O(1).
Initialization from an array is O(N).
The heap accepts a comparator to determine how
elements are compared. The default comparator is defaultComparator and makes
a max-heap. In this case, top will return the greatest element in the
heap.
If a reverseComparator is passed to init,
top will return the minimal element.
- record heap¶
- type eltType¶
The type of the elements contained in this heap.
- param parSafe = false¶
If true, this heap will perform parallel safe operations.
- var comparator: record¶
Comparator record that defines how the data is compared. The greatest element will be on the top.
- proc init(type eltType, param parSafe = false, comparator: record = defaultComparator)¶
Initializes an empty heap.
- Arguments
eltType – The type of the elements
comparator – The comparator to use
parSafe : param bool – If true, this heap will use parallel safe operations.
- proc init=(other: heap(this.type.eltType))¶
Initializes a heap containing elements that are copy initialized from the elements contained in another heap.
- Arguments
other – The heap to initialize from.
- proc size: int¶
Return the size of the heap.
- Returns
The size of the heap
- Return type
int
- proc isEmpty(): bool¶
Returns true if the heap is empty (has size == 0), false otherwise
- Returns
true if this heap is empty.
- Return type
bool
- proc top()¶
Return the top element in the heap.
- Returns
The top element in the heap
- Return type
eltType
- proc push(in element: eltType)¶
Push an element into the heap.
- Arguments
element : eltType – The element to push
- proc push(const ref x: list(eltType))
Push elements of a list into the heap.
- Arguments
x : list(eltType) – The list of elements to push
- proc push(const ref x: [?d] eltType)
Push elements in an array into a heap.
- Arguments
x : [?d] eltType – The array of elements to push
- proc pop(): eltType¶
Pop an element and return it.
- Returns
the top element
- Return type
eltType
- iter these() ref¶
Iterate over the elements of this heap in an arbitrary order.
- iter consume()¶
Iterate over the elements of this heap in order, while removing the yielded elements.
- proc toArray(): [] eltType¶
Returns a new array containing a copy of each of the elements contained in this heap in arbitrary order.
- Returns
A new array.
- proc writeThis(ch: channel) throws¶
Write the contents of this heap to a channel in arbitrary order.
- Arguments
ch – A channel to write to.
- operator heap. = (ref lhs: heap(?t, ?), ref rhs: heap(t, ?))
Copy elements to this heap from another heap.
- Arguments
lhs – The heap to assign to.
rhs – The heap to assign from.
- proc createHeap(const ref x: list(?t), param parSafe: bool = false, comparator = defaultComparator)¶
Create a heap from a list.
- Arguments
x : list(?t) – The list to initialize the heap from.
comparator – The comparator to use
- Return type
heap(t, comparator)
- proc createHeap(const ref x: [?d] ?t, param parSafe: bool = false, comparator = defaultComparator)
Create a heap from an array.
- Arguments
x : [?d] ?t – The array to initialize the heap from.
comparator – The comparator to use
- Return type
heap(t, comparator)