Heap

Usage

use Heap;

or

import Heap;

This module contains the implementation of the 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.
proc =(ref lhs: ?theap?, ref rhs: theap?)

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)