[MathJax off]

3 Heaps

3.1 Introduction

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, Pushing data onto the heap, Peeking at the topmost item, and Popping 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 )

3.2 API

For the purposes of the datastructures, we provide a category IsHeap (3.2-1) . Every implementation of a heap in the category IsHeap (3.2-1) must follow the API described in this section.

3.2-1 IsHeap

Returns: true or false

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

3.2-2 Heap

Wrapper function around constructors

3.2-3 NewHeap

Returns: a heap

Construct a new heap

3.2-4 Push

Puts the object object a new object onto heap.

3.2-5 Peek

Inspect the item at the top of heap.

3.2-6 Pop

Returns: an object

Remove the top item from heap and return it.

3.2-7 Merge

Merge two heaps (of the same type)

Heaps also support IsEmpty (Reference: IsEmpty) and Size (Reference: Size)

3.3 Binary Heaps

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

3.3-1 BinaryHeap

Returns: A binary heap

Constructor for binary 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.

3.4 Pairing Heaps

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].

3.4-1 PairingHeap

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.

3.5 Declarations

3.5-1 IsBinaryHeapFlatRep

Returns: true or false

3.6 Implementation

3.6-1 IsPairingHeapFlatRep

Returns: true or false

generated by GAPDoc2HTML