A *heap* is a tree datastructure such that for any child C of a node N it holds that C \leq N, according to some ordering relation \leq.

The fundamental operations for heaps are Construction, `Push`

ing data onto the heap, `Peek`

ing at the topmost item, and `Pop`

ping the topmost item off of the heap.

For a good heap implementation these basic operations should not exceed O(\log n) in runtime where n is the number of items on the heap.

We currently provide two types of heaps: Binary Heaps 3.3 and Pairing Heaps 3.4.

The following code shows how to use a binary heap.

gap> h := BinaryHeap(); <binary heap with 0 entries> gap> Push(h, 5); gap> Push(h, -10); gap> Peek(h); 5 gap> Pop(h); 5 gap> Peek(h); -10

The following code shows how to use a pairing heap.

gap> h := PairingHeap( {x,y} -> x.rank > y.rank ); <pairing heap with 0 entries> gap> Push(h, rec( rank := 5 )); gap> Push(h, rec( rank := 7 )); gap> Push(h, rec( rank := -15 )); gap> h; <pairing heap with 3 entries> gap> Peek(h); rec( rank := -15 ) gap> Pop(h); rec( rank := -15 )

For the purposes of the **datastructures**, we provide a category `IsHeap`

(???) . Every implementation of a heap in the category `IsHeap`

(???) must follow the API described in this section.

`‣ IsHeap` ( arg ) | ( filter ) |

Returns: `true`

or `false`

The category of heaps. Every object in this category promises to support the API described in this section.

`‣ Heap` ( arg ) | ( function ) |

Wrapper function around constructors

`‣ NewHeap` ( [filter, func, data] ) | ( operation ) |

Returns: a heap

Construct a new heap

`‣ Push` ( heap, object ) | ( operation ) |

Puts the object `object` a new object onto `heap`.

`‣ Peek` ( heap ) | ( operation ) |

Inspect the item at the top of `heap`.

`‣ Pop` ( heap ) | ( operation ) |

Returns: an object

Remove the top item from `heap` and return it.

`‣ Merge` ( heap1, heap2 ) | ( operation ) |

Merge two heaps (of the same type)

Heaps also support `IsEmpty`

(Reference: IsEmpty) and `Size`

(Reference: Size)

A binary heap employs a binary tree as its underlying tree datastructure. The implemenataion of binary heaps in **datastructures** stores this tree in a flat array which makes it a very good and fast default choice for general purpose use. In particular, even though other heap implementations have better theoretical runtime bounds, well-tuned binary heaps outperform them in many applications.

For some reference see http://stackoverflow.com/questions/6531543

`‣ BinaryHeap` ( [isLess[, data]] ) | ( function ) |

Returns: A binary heap

Constructor for binary heaps. The optinal argument `isLess` must be a binary function that performs comparison between two elements on the heap, and returns `true`

if the first argument is less than the second, and `false`

otherwise. Using the optional argument `data` the user can give a collection of initial values that are pushed on the stack after construction.

A pairing heap is a heap datastructure with a very simple implementation in terms of **GAP** lists. `Push`

and `Peek`

have O(1) complexity, and `Pop`

has an amortized amortised O(log n), where n is the number of items on the heap.

For a reference see [FSST86].

`‣ PairingHeap` ( [isLess[, data]] ) | ( function ) |

Returns: A pairing heap

Constructor for pairing heaps. The optional argument `isLess` must be a binary function that performs comparison between two elements on the heap, and returns `true`

if the first argument is less than the second, and `false`

otherwise. Using the optional argument `data` the user can give a collection of initial values that are pushed on the stack after construction.

`‣ IsBinaryHeapFlatRep` ( arg ) | ( filter ) |

Returns: `true`

or `false`

`‣ IsPairingHeapFlatRep` ( arg ) | ( filter ) |

Returns: `true`

or `false`

generated by GAPDoc2HTML