Heap

Usage

use Heap;

or

import Heap;

Warning

The ‘Heap’ module is unstable

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 an instance of 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 : writeSerializable

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 = new DefaultComparator())

Initializes an empty heap.

Arguments:

• eltType – The type of the elements

• parSafe : param bool – If true, this heap will use parallel safe operations.

• comparator – The comparator to use

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 ref 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 ref 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 serialize(writer, ref serializer) throws

Write the contents of this heap to a fileWriter in arbitrary order.

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: ? = new DefaultComparator())

Create a heap from a list.

Arguments:

• x : list(?t) – The list to initialize the heap from.

• parSafe : param bool – If true, this heap will use parallel safe operations.

• comparator – The comparator to use

Return type:

heap(t, comparator)

proc createHeap(const ref x: [?d] ?t, param parSafe: bool = false, comparator: ? = new DefaultComparator())

Create a heap from an array.

Arguments:

• x : [?d] ?t – The array to initialize the heap from.

• parSafe : param bool – If true, this heap will use parallel safe operations.

• comparator – The comparator to use

Return type:

heap(t, comparator)