[boost] [GSoC] Binomial and Fibonacci heap implementation project

Subject: [boost] [GSoC] Binomial and Fibonacci heap implementation project
From: óÕ×ÏÒÏ× äÍÉÔÒÉÊ (dmitriy_suvorov_at_[hidden])
Date: 2010-04-07 03:36:20

Hello,
My name is Dmitriy. I'd like to participate in GSoC2010 with the Boost project. I looked through you ideas list, and I 
think i could do Binomial heap and Fibonacci heap as a summer project. 
I've composed a draft of my proposal, could you comment on it?

My name is Dmitriy Suvorov. I'm a student of Bauman Moscow State Technical University. I am a third course student of a 
Robotics department. My degree program is BS. My email is dmitriy_suvorov_at_inbox.ru. I don't have any homepage. 
I plan to spend 5-5.5 hours per day on coding in June and 8 hours per day in July and August. I plan to start coding on 
May 24th. And I am going to stop coding on 30th August. I can't spend more time in June because I have university's 
exams. I think I won't spend much time on coding in September because university courses will start.  But I am going to 
continue my work on Boost library in autumn.
        My middle degree in university is 4.76 (maximum is 5.0). I've taken courses in mathematics, programming and 
electronics. I'm interested in coding with application of mathematical algorithms. Now I'm working on robotics computer 
vision to participate in international competitions "Eurobot 2010". I'm going to take part in open source project for 
the first time.
        I'm interested in contributing to the Boost C++ Libraries and I want to gain an experience in programming. I'd 
like to solve interesting problems. I have knowledge about data structures and want to apply my knowledge in practice. 
I'm going to read more information about data structures and Boost C++ Libraries in May.
My rates, from 0 to 5 (0 being no experience, 5 being expert), of my knowledge of the following languages, technologies, 
or tools:
         C++   -  5
         C++ Standard Library  -  5
         Boost C++ Libraries   - 3
         Subversion   - 4
I like Visual Studio to write Windows programs and KDevelop to write Linux programs. The most familiar software 
documentation tool with me is Doxygen.
        I want to work on binomial heap. If I'll solve problem quickly I want to work on other data structure, for 
example, on Fibonacci heap.
        Binomial heap is implementation of the mergeable heap abstract data type which is a priority queue supporting 
merge operation. Binomial heap is a collection of binomial trees. A binomial tree is defined recursively:
-	A binominal tree of order 0 is a single node.
-	A binomial tree of order k has a root node whose children are roots of binomial trees of orders k-1, k-2, +, 1, 
0.
All operations work on O(log n) time on a binomial heap with n elements.
Fibonacci heap is a heap data structure consisting of a forest of trees. It has a better amortized running time than a 
binomial heap.
These heaps are used in to improve asymptotic time of important algorithms, such as Dijkstra's algorithm for computing 
shortest path in a graph, and Prim's algorithm for computing a minimum spanning tree of a graph.
I have found implementations of binomial heap in C and Python at LITMUS project. The homepage of project is 
www.cs.unc.edu/~anderson/litmus-rt/ .
I'm going to create a new class for the Binominal heap and polish current implementation of Fibonacci heap.
I will use Introduction to algorithms by Cormen, Leiserson as a reference.
Could you review this?