C++程序员常见面试题总结

template<typename T> class minHeap { private: T* heapArray; int currentSize; int maxSize; void swap(int pos1,int pos2); void buildHeap(); public: minHeap(const int& n); vitual ~minHeap(); bool isempty(); bool isLeaf(int pos) const; int leftchild(int pos) const; int rightchild(int pos) const; int parent(int pos) const; bool remove(int pos); bool insert(const T& value); T& removeMin(); void siftup(int pos); void siftdown(int pos); }; template<typename T> minHeap<T>::minHeap(const int& n) { if(n<=0) { return; } currentSize = 0; maxSize = n; heapArray = new T[maxSize]; buildHeap(); } template<typename T> minHeap<T>::~minHeap() { currentSize = 0; maxSize = 0; delete[] heapArray; } template<typename T> minHeap<T>::buildHeap() { for(int i=currentSize/2-1;i>=0;--i) { siftdown(i); } } template<typename T> bool minHeap<T>::isempty() { return 0==currentSize; } template<typename T> bool minHeap<T>::isLeaf(int pos) const { return (pos>=currentSize/2)&&(pos<maxSize); } template<typename T> int minHeap<T>::leftchild(int pos) const { return 2*pos+1; } template<typename T> int minHeap<T>::rightchild(int pos) cosnt { return 2*pos+2; } template<typename T> int minHeap<T>::parent(int pos) const { return (pos-1)/2; } template<typename T> bool minHeap<T>::insert(const T& value) { if(currentSize==maxSize) return false; heapArray[currentSize] = value; siftup(currentSize) currentSize++; return true; } template<typename T> bool minHeap<T>::remove(int pos) { if(pos<0&&pos>=currentSize) return false; swap(pos,currentSize-1); currentSize--; if(heapArray[parent(pos)]>heapArray[pos]) { siftup(pos); } else { siftdown(pos); } } template<typename T> int minHeap<T>::removeMin(int pos) { if(currentSize==0) return false; swap(0,currentSize-1); currentSize--; if(currentSize>1) { siftdown(0); } return heapArray[currentSize]; } template<typename T> void minHeap<T>::siftup(int pos) { int cur = pos; T temp = heapArray[pos]; while(cur>0&&heapArray[parent[cur]]>temp) { heapArray[cur] = heapArray[parent(cur)]; cur = parent(cur); } heapArray[cur] = temp; } template<typename T> void minHeap<T>::siftdown(int pos) { int cur = pos; int temp = heapArray[pos]; int leftchild = leftchild(cur); while(leftchild<currentSize) { if(leftchild<currentSize-1&&heapArray[leftchild+1]<heapArray[leftchild]) { leftchild++; } if(heapArray[leftchild]<temp) { heapArray[cur] = heapArray[leftchild]; cur = leftchild; leftchild = leftchild(cur); } else { break; } } heapArray[cur] = temp; }