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

Subject: Re: [boost] [GSoC] Binomial and Fibonacci heap implementation project
From: Andrew Sutton (andrew.n.sutton_at_[hidden])
Date: 2010-04-07 07:24:54

Hi Dmitriy,

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

Your proposal doesn't really tell me how you plan to achieve these goals.
It's also important to relate your work to any previous or similar
implementations in Boost. This particular project seems to be attracting a
large number of proposals. In order to be competitive, you'll need to
demonstrate some particular insights into the project that differentiate
your proposal from others.

Andrew Sutton
andrew.n.sutton_at_[hidden]