##
Heaps

This page contains various heap implementations.

[Download]

Separate C source files are provided for each heap implementation
and are used by some of the algorithms in this repository.

[Binary
Heap, Fibonacci
Heap, 2-3
Heap, Trinomial
Heap]

### Common Files

A description
of all the heaps implemented is provided.

The header file heap_info.h defines a
common structure type for heaps so that they can be used
interchangeably. A program which uses this
common structure type is then able to use different heaps
interchangeably.
The heap implementation of Dijkstra's algorithm is an example of this.

### Binary Heap

### Fibonacci Heap

### 2-3 Heap

The trees in a 2-3 heap can be viewed in two different ways, and this
leads
to two different 2-3 heap implementations.
Implemented using linked lists of child nodes:

Implemented using linked lists of child node-pairs:
In the node-pair implementation the linked list of child nodes is
defined
differently. Nodes have an extra pointer which points to an
optional
partner node with which the node forms a node-pair. Each node has
a boolean field which identifies whether it is the "extra" node a
node-pair.
### Trinomial heap

The extended trinomial heap implementation supports O(1) worst case
time
for decrease_key:
The basic trinomial heap implementation supports O(1) amortized time
for
decrease_key: