一个最小堆的C++模板。什么东西都想封装成类，做成模板，即使它仅仅就是一个普通的函数，尤其是用到一些全局的对象时，觉得封装成类看起来更紧凑一点，使用起来也更方便更顺手一些。这个最小堆模板实现了以下几个小特性：
容量不足时，能够动态地调整大小；
可以用一个数组来初始化，并建立最小堆；
没有复制构造，^*^.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 | template <class T> class Heap { public: //~ 构造容量n的堆 Heap(size_t n = 64); //~ 以数组构造 Heap(const T* beg, const T* end); ~Heap(){delete [] pHeap;} //~ 添加元素 void push(const T& item); //~ 返回并删除堆顶元素 T pop(); //~ 返回堆顶元素的引用 T& top()const;//! 不允许修改！ size_t size() const;//~ 当前元素个数 size_t capacity() const;//~ 当前容量 private: void resize();//~ 重新调整堆容量 void adjust(int i);//~ 调整以i为根的子树为最小堆 T * pHeap; size_t _size; size_t _capacity; }; template <class T> Heap<T>::Heap(size_t n): pHeap(new T[n]) { _size = 0; _capacity = n; } template <class T> Heap<T>::Heap(const T* beg,const T* end) { _capacity = _size = end - beg; pHeap = new T[_size]; for(int i = 0; i < _size; ++i) { pHeap[i] = *beg++; } int i = _size - 1; //~ 调用adjust(int)构造最小堆 for( ; i >= 0; --i) adjust(i); } template <class T> void Heap<T>::push(const T& item) { //~ 容量不足时重新分配空间 if(_size == _capacity) resize(); _size++; int i = _size - 1; //~ 通过上溯寻找合适的插入位置 while(i && pHeap[(i-1)/2] > item) { pHeap[i] = pHeap[(i-1)/2]; i = (i-1) / 2; } pHeap[i] = item; } template <class T> T Heap<T>::pop() { //~ assert(_size); if(_size <= 0)exit(1); T rt = pHeap[0]; //~ 先将堆尾元素置顶，然后重建 pHeap[0] = pHeap[--_size]; if(_size) adjust(0); return rt; } template <class T> T& Heap<T>::top()const { // assert(_size); if(_size <= 0)exit(1); return pHeap[0]; } template <class T> size_t Heap<T>::size()const { return _size; } template <class T> size_t Heap<T>::capacity()const { return _capacity; } template <class T> void Heap<T>::resize() { T * org = pHeap; //~ 调整容量 _capacity = 2*_capacity + 1; pHeap = new T[_capacity]; //~ 复制堆 for(int i = 0; i < _size; ++i) { pHeap[i] = org[i]; } delete [] org; } template <class T> void Heap<T>::adjust(int i) { //~ 重建以i为根的最小堆，假定其左右子树已是最小堆 size_t minpos; while(2 * i + 1 < _size) { minpos = i; if(2 * i + 2 < _size && pHeap[2*i+2] < pHeap[i]) minpos = 2 * i + 2; if(pHeap[2*i+1] < pHeap[minpos]) minpos = 2 * i + 1; if(minpos == i) break; swap(pHeap[i], pHeap[minpos]); i = minpos; } } |
你好！除了代码，此处没有多少原创之物，皆为本人搜集、整理、总结之记录与心得，欢迎转载分享！转载时请尽量注明出处，将不胜感激。祝你健康、快乐！
支持一下。