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: