[GSoC] Binomial and Fibonacci heap implementation project
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@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?
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@gmail.com
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@gmail.com
During work on binomial heap I'm going to implement these classes: #ifndef BOOST_BINOMIAL_HEAP_HPP #define BOOST_BINOMIAL_HEAP_HPP #include #include <boost/property_map/property_map.hpp> template <typename T, class ID=identity_property_map> class binomial_node { typedef typename boost::property_traits<ID>::value_type size_type; public: typedef T value_type; value_type _key; binomial_node *_p; binomial_node *_child; binomial_node *_sibling; size_type _degree; binomial_node(value_type key, const ID& id=identity_property_map()); }; //Class of pointer to node of binomial heap. template <typename T, class ID=identity_property_map> class const_node_pointer { protected: const binomial_node<T,ID>* ptr; public: node_pointer(); const binomial_node<T,ID>::value_type& operator->() const; }; //Class of binomial heap. template <typename T, class Compare=std::less<T>, class ID=identity_property_map> class binomial_heap { typedef typename boost::property_traits<ID>::value_type size_type; typedef binomial_node<T,ID>::value_type value_type; typedef binomial_node<T,Compare,ID> node_type; protected: Compare _compare; node_type _head,_min_key; bool min_key_valid; ID _id; //Merge head's lists of this heap and "heap" and sort them by degrees. //This method will be necessary to relize "heap_union". void heap_merge(const binomial_heap& heap); //Make node y new head of list of node's y children. //This function will be necessary to relize "heap_union". static void Link(binomial_node& y,binomial_node& z); public: //Default constructor binomial_heap(); //Copy constructor. binomial_heap(const binomial_heap& heap); //Destructor. ~binomial_heap(); //Find the element with minimum key. const const_node_pointer& minimum() const; //Merge two heaps to one heap. void heap_union(binomial_heap& heap); //Insert a new element to the heap. const const_node_pointer& insert(const value_type& new_key); //Delete the element with minimum key from the heap. value_type extract_min(); //Decrease key of a given element. //Return false if old key is less than new one. bool decrease_key(const const_node_pointer& node,value_type new_key); //Delete given element from the heap void delete_element(const const_node_pointer& node); //Is there any elements in the heap? bool empty(); binomial_heap& operator=(const binomial_heap& heap); }; #endif I'm going to use an additional pointer to the element with minimum key and update it during searching for element with minimum key, extracting element with minimum key and inserting a new element to the heap. Do you think any other are methods necessary? Must I code operator !, operator == or any other operators? After this I could add some additional methods and operators for Fibonacci heap.
on 07.04.2010 at 11:36 Суворов Дмитрий wrote :
My name is Dmitriy Suvorov. I'm a student of Bauman Moscow State Technical University... бауманка форева!!! удачи с проектом!
translation: BMSTU rules!!! good luck with your project! sorry for my sentimentality -- Pavel P.S. if you notice a grammar mistake or weird phrasing in my message please point it out
Wed, 7 Apr 2010 19:47:53 +0400 письмо от DE <satan66613@yandex.ru>:
on 07.04.2010 at 11:36 Суворов Дмитрий wrote :
My name is Dmitriy Suvorov. I'm a student of Bauman Moscow State Technical University... бауманка форева!!! удачи с проектом!
translation: BMSTU rules!!! good luck with your project!
sorry for my sentimentality
-- Pavel P.S. if you notice a grammar mistake or weird phrasing in my message please point it out
Thanks!!! Good luck you too!!!
participants (3)
-
Andrew Sutton -
DE -
Суворов Дмитрий