This page contains various heap implementations.
Separate C source files are provided for each heap implementation
and are used by some of the algorithms in this repository.
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
The heap implementation of Dijkstra's algorithm is an example of this.
The trees in a 2-3 heap can be viewed in two different ways, and this
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
differently. Nodes have an extra pointer which points to an
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
The extended trinomial heap implementation supports O(1) worst case
The basic trinomial heap implementation supports O(1) amortized time