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: fileWriter) 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)