利用STL实现一个Heap

  发现STL里有个现成的Heap算法,就拿来包装了一下,然后用它写了个A*来解8数码。虽然不一定是最优解,但速度确实快了好多。
  现在把那个Heap的代码贴出来。很简单的吧。有STL就是好。

//需要include algorithm和vector
template
class Heap {
public:
    Heap(){
        make_heap(data.begin(), data.end());
    }
   
    void push(_type entry){
        data.push_back(entry);
        push_heap(data.begin(), data.end());
    }
   
    _type top(){
        return *(data.begin());
    }
   
    _type pop(){
        _type ret;
        ret = top();
        pop_heap(data.begin(), data.end());
        data.pop_back();
        return ret;
    }
   
    bool empty(){
        return size() == 0;
    }
   
    bool clear(){
        data.clear();
        make_heap(data.begin(), data.end());
    }
   
    int size(){
        return data.size();
    }
private:
    vector<_type> data;
};

2 thoughts on “利用STL实现一个Heap

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.