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

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

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

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.