+ -
当前位置:首页 → 问答吧 → 极小堆-Min_heap......

极小堆-Min_heap......

时间:2011-12-07

来源:互联网

看了一个极大堆的实现,大概明白了,于是心血来潮想写一个极小堆的实现,可是。。。写出来,结果有点尴尬= =!!

(有代码,才说话!)
C/C++ code

template <typename T, class ty_>//Wrong in inheriting class vector<T>
struct Min_heap:vector<T>
{
    typedef vector<T>  me_;

    Min_heap(void):me_(){}//Suspected here

    bool empty(void) const {return me_::empty();}
    int size(void) const {return me_::size();}
    //T& operator [](int n){return me_.elem_[n];}
    T const& top(void) const {return me_[0];}

    void shiftup_min(T* a, int n)
    {
        for (int p = n/2; p>0 && a[p] > a[n]; p = (n = p)/2)
            swap(a[p],a[n]);
    }

    void shiftdown_min(T* a, int n)
    {
        for (int p = 1, bc = 2; bc <= n; bc = 2*p)
        {
            if (bc < n && a[bc] > a[bc+1])
                ++bc;
            if (a[p] > a[bc])
            {
                swap(a[p],a[bc]);
                p = bc;
            }
            else 
                break;
        }
    }
    void push(T const& v)
    {
        me_::push_back(v);
        T* const a = &me_[0] - 1;
        shiftup_min(a,me_::size());
    }

    void pop(void)
    {
        int const n = me_::size() - 1;
        swap (me_[0], me_[n]);
        T* const a = &me_[0] - 1;
        shiftdown_min(a, n);
        me_::pop_back();
    }

};



error C2275: 'Min_heap<int,struct Huffman_less>::me_' : illegal use of this type as an expression
while compiling class-template member function 'const int &__thiscall Min_heap<int,struct Huffman_less>::top(void) const'
执行 cl.exe 时出错.

请教各位这是怎么回事。。怀疑有问题的地方我标出来了一个,另外可能还有没标出来的。。= =!
以分数为谢。

作者: lrcry   发布时间: 2011-12-07

C/C++ code

typedef vector<T>  me_;//这里me_是类型名
me_::size();,me_::empty();//这里empty函数肯定不会是static函数

me_[0];//这里me_又是当成对象使用的


//如果楼主本意是将me_定义为对象的话,可以做如下修改
typedef vector<T>  me_; --> vector<T>  me_;
me_:: --> me_.

作者: we_sky2008   发布时间: 2011-12-07

修改替换之后为:
C/C++ code

template <typename T, class ty_>
struct Min_heap:vector<T>
{
    vector<T>  me_;

    Min_heap(void) : me_(){}

    bool empty(void) const {return me_.empty();}
    int size(void) const {return me_.size();}
    T& operator [](int n){return me_.elem_[n];}
    T const& top(void) const {return me_[0];}

    void shiftup_min(T* a, int n)
    {
        for (int p = n/2; p>0 && a[p] > a[n]; p = (n = p)/2)
            swap(a[p],a[n]);
    }

    void shiftdown_min(T* a, int n)
    {
        for (int p = 1, bc = 2; bc <= n; bc = 2*p)
        {
            if (bc < n && a[bc] > a[bc+1])
                ++bc;
            if (a[p] > a[bc])
            {
                swap(a[p],a[bc]);
                p = bc;
            }
            else 
                break;
        }
    }
    void push(T const& v)
    {
        me_.push_back(v);
        T* const a = &me_[0] - 1;
        shiftup_min(a,me_.size());
    }

    void pop(void)
    {
        int const n = me_.size() - 1;
        swap (me_[0], me_[n]);
        T* const a = &me_[0] - 1;
        shiftdown_min(a, n);
        me_.pop_back();
    }
};

作者: we_sky2008   发布时间: 2011-12-07

引用 2 楼 we_sky2008 的回复:
修改替换之后为:

C/C++ code


template <typename T, class ty_>
struct Min_heap:vector<T>
{
vector<T> me_;

Min_heap(void) : me_(){}

bool empty(void) const {return me_.empty();}
……


大概看明白了2楼的意思。。是我的一时疏忽哈
不过 ,为嘛照这么修改了之后,我所有的swap函数都被报错了
error C2660: 'swap' : function does not take 2 parameters

在STL里面,参数明明是两个嘛。。这个函数 本身不就是用来交换两个键值的吗。。 - -
求教了。。。

作者: lrcry   发布时间: 2011-12-07

热门下载

更多