C++实现一个堆（模板）

àì夳堔傛蜴生んèń 2022-06-15 00:00 113阅读 0赞

堆是一个很基础的数据结构，在stl里面有封装`make_heap`、`push_heap`等操作，这两天看到libevent用小根堆实现Timer，就想实现一个简单的堆。

## 基本概念 ##

堆的实现通过构造二叉堆（binary heap），实为二叉树的一种；由于其应用的普遍性，当不加限定时，均指该数据结构的这种实现。这种数据结构具有以下性质。

> 任意节点小于（或大于）它的所有后裔，最小元（或最大元）在堆的根上（堆序性）。  
> 堆总是一棵完全树。即除了最底层，其他层的节点都被元素填满，且最底层尽可能地从左到右填入。

将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。

简单来说，堆的存储结构是数组，逻辑结构是一棵完全二叉树，通过索引的方式表示二叉树父节点和孩子节点的关系，父节点大于孩子节点叫大根堆，反之叫小根堆．堆支持的主要操作有：入堆，出堆，调堆，堆排序，其中插入操作复杂度为O(logn)，因此堆排序的复杂度是O(nlogn)

## 实现 ##

主要实现几个操作`push`，`pop`，`sort`：

### １．插入： ###

也就是，首先插入一定是插入到完全二叉树的最右下，对应数组中，也就是`back()`的位置，那么为了满足堆的性质，就需要不断的上溯，也就是将新插入的元素往上到合适的位置．这里沿用ＳＴＬ中的实现方式，并不是直接的swap，而是先生成一个`HoleInex`也就是产生一个空洞，这个空洞就是待插入的位置，但是这个空洞需要不断的上溯到合适位置，然后将新值插入即可．

### ２．弹出： ###

弹出堆中的最大值/最小值，对应的就是堆顶元素，数组索引位置为0或者1（取决于实现）。这个时候将堆顶元素放到末尾（覆盖最后一个元素），堆顶的这个位置就变成了空洞了，此时需要将原来的末尾的元素插入到这个空洞中，就需要将这个空洞下沉到合适位置，然后将元素插入，并且堆大小减1

### ３．排序： ###

`pop`操作每次都会弹出最大或者最小的元素到堆尾，那么执行n-1次弹出操作，数组就有序了。

## 代码 ##

#include <iostream>
    #include <vector>
    #include <boost/function.hpp>
    #include <boost/bind.hpp>
    #include <iterator>
    using namespace std;
    
    using namespace boost;
    
    #define dumpheap  0x0001
    #define dumparray 0x0010
    
        template <class T>
    bool less_(const T &t1,const T& t2)
    {
        return t1<t2;
    }
    
        template <class T>
    bool greater_(const T &t1,const T& t2)
    {
        return t1>t2;
    }
    
    template <class T>
    class myHeap{
        typedef boost::function<bool (const T &,const T&)> comp;
        private:
        void up(int ,T);
        comp f;
        public:
        myHeap(comp f_=greater_<T>):size_(0),f(f_){heap_.reserve(1024);}
        ~myHeap(){}
        vector<T> heap_;
        int size_;
        void push(T t);
        void pop();
        void sort_heap();
        void adjust(int , T);
        void dump(int flag=dumpheap)
        {
            if(flag & dumpheap)
            {
                copy(heap_.begin(),heap_.begin()+size_,ostream_iterator<T>(cout," "));
                cout << endl;
            }
            else if(flag & dumparray)
            {
                copy(heap_.begin(),heap_.end(),ostream_iterator<T>(cout," "));
                cout << endl;
    
            }
        }
    
    };
    #if 1
        template <class T>
    void myHeap<T>::adjust(int holeindex,T t)
    {
        int r=2*holeindex + 2;
        int l=2*holeindex + 1;
        while(r< size_)
        {
    
            if(f(heap_[r],heap_[l]))
                --r;
    
            heap_[holeindex]=heap_[r];
            holeindex=r;
            r=2*r+2;
        }
        if(r==size_)
        {
            heap_[holeindex]=heap_[r-1];
            holeindex=r-1;
        }
        heap_[holeindex]=t;
        up(holeindex,t);//上溯操作
    
    }
    #endif
    
    
        template <class T>
    void myHeap<T>::push(T t)
    {
        heap_.push_back(t);
    
        int holeindex=size_;
        ++size_;
        up(holeindex,t);
    
    }
    
        template <class T>
    void myHeap<T>::sort_heap()
    {
        while(size_>1)
        {
            pop();
        }
    }
    
    
        template <class T>
    void myHeap<T>::pop()
    {
        T t=heap_[size_-1];//最后一个元素
        heap_[size_-1]=heap_[0];//将根元素放到最后
    
        --size_;
        adjust(0,t);
    }
    
        template <class T>
    void  myHeap<T>::up(int holeindex,T t)
    {
        int parent=(holeindex-1)/2;
    
        while(holeindex > 0 && f(heap_[parent],t))
        {
            heap_[holeindex]=heap_[parent];//父节点下溯
            holeindex=parent; //hole节点上溯
            parent=(holeindex-1)/2;
        }
        heap_[holeindex]=t;
    }
    
    
    
    int main()
    {
        cout << dumparray<<endl;
    #if 1
        myHeap<int> h(less_<int>);
        h.push(5);
        h.push(4);
        h.push(3);
        h.push(2);
        h.push(1);
    
    
    #if 1
        cout<<"before sort"<<endl;
        h.dump();
        h.sort_heap();
        cout<<"after sort heap dump" << endl;
        h.dump();
        cout<<"after sort array dump"<<endl;
        h.dump(dumparray);
    #endif
    #endif
    //    h.sort_heap();
    
        return 0;
    }

## 参考 ##

比较详细的解释：  
1，侯捷 STL源码剖析  
2，[http://blog.csdn.net/xiajun07061225/article/details/8553808][http_blog.csdn.net_xiajun07061225_article_details_8553808]  
3，[http://blog.csdn.net/zhangxiao93/article/details/51330582][http_blog.csdn.net_zhangxiao93_article_details_51330582]  
4，[http://blog.csdn.net/zhangxiao93/article/details/51333205][http_blog.csdn.net_zhangxiao93_article_details_51333205]

[http_blog.csdn.net_xiajun07061225_article_details_8553808]: http://blog.csdn.net/xiajun07061225/article/details/8553808
[http_blog.csdn.net_zhangxiao93_article_details_51330582]: http://blog.csdn.net/zhangxiao93/article/details/51330582
[http_blog.csdn.net_zhangxiao93_article_details_51333205]: http://blog.csdn.net/zhangxiao93/article/details/51333205