Data Structures
Most of the code that I write requires little more than linked lists or arrays with the occasional map or hash table. All of these are implemented for C++ in the STL so I rarely get a chance to actually implement any interesting data structures. I decided that that was a real shame and spent a couple of weeks implementing a few of the more interesting data structures: a binomial heap, a Fibonacci heap and a red-black tree. Some of these aren’t completely finished, none of them have been thoroughly tested (although as far as I know they work) and some have some debugging code left in. Maybe someday I’ll revisit the code and clean it up a bit.
A binomial heap consists of a forest of trees where each tree satisfies the min-heap property. The trees are defined recursively so that a tree of size n will have n children of size (n-1) to 1. When I first started to read up on how they are designed, I found it rather strange that the first operation covered by the CLRS was the merge. Intuitively it makes more sense to start with insertion, however as I soon discovered almost every operation performed on it is a variation of the merge operation. I soon realized the elegance of the design of the binomial heap. If you want to insert a node into a binomial heap, create a new heap containing one element and merge the two heaps. If you want to delete the minimum element, remove it. It’s children are a forest of trees (which obviously all satisfy the min-heap property) making them a binomial heap, so merge the two heaps.
*Download the source code for the Binomial heap
A Fibonacci heap is similar to a binomial heap but the structure of the heap is relaxed to allow deferment of operations. This results in better amortized bounds on certain operations (namely insertion and decrease key). Of course this relaxation results in a loss of elegance.
*Download the source code for the Fibonacci heap
A Red-black tree is a balanced binary tree. To maintain a balance, there are certain invariants imposed on the tree: 1) each node in the tree is colored either red or black, 2) the root is always black, 3) all the leaves are black and 4) every path from a node to any descendant leaf contains the same number of black nodes. These invariants are enforced through re-coloring and tree rotations.