最小堆

#include<iostream> #include<queue> //试着加加const using namespace std; const int defaultSize=10; template<class T> class MinHeap { public: MinHeap(int sz = defaultSize); MinHeap(T arr[], int n); ~MinHeap() { delete[] heap; } bool push(const T& x); bool pop(); T top(); bool empty() const { return(currentsize == 0) ? true : false; } bool isFull() const { return(currentsize == maxHeapsize) ? true : false; } private: T* heap; int currentsize; int maxHeapsize; void siftDown(int start, int m); void siftUp(int start); }; template<class T> MinHeap<T>::MinHeap(int sz) { maxHeapsize = (defaultSize < sz) ? sz : defaultSize; heap = new T[maxHeapsize]; if (heap == NULL) cout << "分配失败" << endl; currentsize = 0; } template<class T> MinHeap<T>::MinHeap(T arr[], int sz) { maxHeapsize = (defaultSize < sz) ? sz : defaultSize; heap = new T[maxHeapsize]; if (heap == NULL) cout << "分配失败" << endl; currentsize = sz; for (int i = 0; i < sz; i++) heap[i] = arr[i]; int currentPos = (currentsize - 2) / 2; while (currentPos >= 0) { siftDown(currentPos, currentsize - 1); currentPos--; } } template<class T> void MinHeap<T>::siftDown(int start, int m) { int i = start, j = 2 * i + 1; T temp = heap[i]; while (j <= m) { if (j<m&&heap[j] > heap[j + 1])j++; if (temp <= heap[j]) break; else { heap[i] = heap[j]; i = j; j = 2 * j + 1; } } heap[i] = temp; } template<class T> void MinHeap<T>::siftUp(int start) { int i = start, j = (i - 1) / 2; T temp = heap[i]; while (j >= 0) { if (heap[j] <= temp)break; else { heap[i] = heap[j]; i = j; j = (j - 1) / 2; } } heap[i] = temp; } template<class T> bool MinHeap<T>::push(const T& x) { if(currentsize==maxHeapsize) { cout << "Heap Full" << endl; return false; } heap[currentsize] = x; siftUp(currentsize); currentsize++; return true; } template<class T> bool MinHeap<T>::pop() { if (empty()) { cout << "Heap Empty" << endl; return false; } T x = heap[0]; heap[0] = heap[currentsize - 1]; currentsize--; siftDown(0, currentsize - 1); return true; } template<class T> T MinHeap<T>::top() { return heap[0]; } int main() { int a[] = { 5,6,2,5,1,7,3,2,1,8 }; MinHeap<int>s(a, 10); while (!s.empty()) { cout << s.top(); s.pop(); } }