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.
- Example program: [Dijkstra's Algorithm]
- Test data - using heaps in Dijkstra's algorithm: 2-3 heap test data, trinomial heap test data
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:
- 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:
