Goto Chapter: Top 1 2 3 4 5 6 7 8 9 10 11 12 Bib Ind
 [Top of Book]  [Contents]   [Previous Chapter]   [Next Chapter] 

3 Heaps
 3.1 Introduction
 3.2 API
 3.3 Binary Heaps
 3.4 Pairing Heaps
 3.5 Declarations
 3.6 Implementation

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

3.2-2 Heap
‣ Heap( arg )( function )

Wrapper function around constructors

3.2-3 NewHeap
‣ NewHeap( [filter, func, data] )( constructor )

Returns: a heap

Construct a new heap

3.2-4 Push
‣ Push( heap, object )( operation )

Puts the object object a new object onto heap.

3.2-5 Peek
‣ Peek( heap )( operation )

Inspect the item at the top of heap.

3.2-6 Pop
‣ Pop( heap )( operation )

Returns: an object

Remove the top item from heap and return it.

3.2-7 Merge
‣ Merge( heap1, heap2 )( operation )

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
‣ BinaryHeap( [isLess[, data]] )( function )

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

3.5 Declarations

3.5-1 IsBinaryHeapFlatRep
‣ IsBinaryHeapFlatRep( arg )( filter )

Returns: true or false

3.6 Implementation

3.6-1 IsPairingHeapFlatRep
‣ IsPairingHeapFlatRep( arg )( filter )

Returns: true or false

 [Top of Book]  [Contents]   [Previous Chapter]   [Next Chapter] 
Goto Chapter: Top 1 2 3 4 5 6 7 8 9 10 11 12 Bib Ind

generated by GAPDoc2HTML