SD.Tools.Algorithmia.Heaps Namespace

Simple heap which is based on a binary tree: the binary heap. See: http://en.wikipedia.org/wiki/Binary_heap Binary heaps are quite efficient, however if you're doing a lot of merging between heaps, the Binary heap is inefficient. Consider a Fibonacci heap instead in these situations.

Implementation of a Fibonacci heap. See: http://en.wikipedia.org/wiki/Fibonacci_heap for details about the Fibonacci heap. A Fibonacci heap is a heap with on average one of the fastest characteristics of all known heap datastructures to date. However, the efficiency is expressed as 'amortized' time, which means it's averaged: the fastest operations are a little slower as some other operations can be rather time consuming in some situations. There are cases where a Binomial heap (http://en.wikipedia.org/wiki/Binomial_heap) would be more efficient, however as in general the Fibonacci heap performs more efficiently, this library contains an implementation of Fibonacci heap instead of a Binomial heap.

Some time ago another variant (actually two variants) of the Fibonacci heap, the 'Relaxed' Fibonacci Heap has been proposed, one has the same characteristics as the Fibonacci heap and one has some operations more efficient. As the implementation of a Relaxed Fibonacci Heap is quite complex we've postponed its implementation till a later date. For more information about Relaxed Fibonacci Heaps, please see: http://www.pmg.lcs.mit.edu/~chandra/publications/heap.pdf Relaxed Fibonacci Heaps have a slight advantage in parallel environments.

General base class for all Heap classes. A heap is a specialized tree-based datastructure which has its elements ordered in such a way that every parent is larger / equal than its children, if the heap is a max-heap and in the case of a min-heap every parent is smaller/equal than its children. See: http://en.wikipedia.org/wiki/Heap_%28data_structure%29
The heap classes implement the basic operations on a heap: delete max/min, increase/decrease key, insert and merge.