浏览 2489 次
锁定老帖子 主题:实用类之二-----最大堆的实现
该帖已经被评为隐藏帖
|
|
---|---|
作者 | 正文 |
发表时间:2007-04-09
template<class T> class MaxHeap{ public: MaxHeap(T a[],int n); MaxHeap(int ms); ~MaxHeap(); bool Insert(const T &x);//插入一个元素,如果空返回false,否则返回true bool RemoveMax(T &x);//删除最小的元素,如果空返回false,否则返回true void MakeEmpty();//使堆为空 bool IsEmpty(); bool IsFull(); protected: void FilterDown(const int start,const int endOfHeap);//自顶向下构造堆 void FilterUp(const int start);//自底向上构造堆 private: T *heap; int maxSize; const int defaultSize; int currentSize; }; template<class T> MaxHeap<T>::MaxHeap(int ms):defaultSize(100){ maxSize = ms > defaultSize ? ms : defaultSize; heap = new T[maxSize]; currentSize = 0; } template<class T> MaxHeap<T>::MaxHeap(T a[],int n):defaultSize(100){ maxSize = n > defaultSize ? n : defaultSize; heap = new T[maxSize]; currentSize = n; for(int i = 0; i < n; i++) heap[i] = a[i]; int curPos = (currentSize - 2) / 2; while(curPos >= 0){ FilterDown(curPos,currentSize - 1); curPos--; } } template<class T> MaxHeap<T>::~MaxHeap(){ delete []heap; } template<class T> void MaxHeap<T>::FilterDown(const int start,const int endOfHeap){ int i = start,j = i * 2 + 1; T temp = heap[i]; while(j <= endOfHeap){ if(j < endOfHeap && heap[j] < heap[j+1]) j++; if(temp > heap[j]) break; else{ heap[i] = heap[j]; i = j; j = 2 * i + 1; } } heap[i] = temp; } template<class T> void MaxHeap<T>::FilterUp(const int start){ int i = start, j = ( i - 1 ) / 2; T temp = heap[i]; while(i > 0){ if(temp <= heap[j]) break; else{ heap[i] = heap[j]; i = j; j = (i - 1) / 2; } } heap[i] = temp; } template<class T> bool MaxHeap<T>::RemoveMax(T &x){ if(IsEmpty()){ cerr<<"Heap empty!"<<endl; return false; } x = heap[0]; heap[0] = heap[currentSize - 1]; currentSize--; FilterDown(0,currentSize-1); return true; } template<class T> bool MaxHeap<T>::Insert(const T& x){ if(IsFull()) { cerr<<"Heap Full!"<<endl; return false; } heap[currentSize] = x; FilterUp(currentSize); currentSize++; return true; } template<class T> bool MaxHeap<T>::IsEmpty(){ return currentSize == 0; } template<class T> bool MaxHeap<T>::IsFull(){ return currentSize == maxSize; } template<class T> void MaxHeap<T>::MakeEmpty(){ currentSize = 0 } MainApp.cpp测试文件: #include<iostream> #include"MaxHeap.h" using namespace std; void main(){ int a[5] = {3,2,1,4,5}; MaxHeap<int> m_heap(a,5); int x,i; for(i = 0; i < 5; i++){ m_heap.RemoveMax(x); cout << x << " "; } cout << endl; for(i = 0; i < 5; i++){ m_heap.Insert(a[i]); } for(i = 0; i < 5; i++){ m_heap.RemoveMax(x); cout << x << " "; } cout << endl; } 声明:ITeye文章版权属于作者,受法律保护。没有作者书面许可不得转载。
推荐链接
|
|
返回顶楼 | |