Algorithm Repository Home Page

Heaps

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.

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

Example program: [Dijkstra's Algorithm]
Test data - using heaps in Dijkstra's algorithm: 2-3 heap test data, trinomial heap test data

Binary Heap

C source files: bheap.c bheap.h

Fibonacci Heap

C source files: fheap.c fheap.h

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:

C source files: ttheap.c ttheap.h
2-3 heap representation using pointers: (picture)

Implemented using linked lists of child node-pairs:

C source files: ttheap2.c ttheap2.h
2-3 heap representation using node-pair pointers: (picture)

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:

C source files: triheap_ext.c triheap_ext.h.
extended trinomial heap representation: (picture)

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

C source files: triheap.c triheap.h.
basic trinomial heap representation: (picture)