C++排序(小堆排序)
发布时间:2020-12-16 07:43:05 所属栏目:百科 来源:网络整理
导读:今天PHP站长网 52php.cn把收集自互联网的代码分享给大家,仅供参考。 #includeiostream #includestring using namespace std; templateclass Type class MinHeap { public: MinHeap(int sz=DefaultSize) { capacity = szD
以下代码由PHP站长网 52php.cn收集自互联网 现在PHP站长网小编把它分享给大家,仅供参考 #include<iostream> #include<string> using namespace std; template<class Type> class MinHeap { public: MinHeap(int sz=DefaultSize) { capacity = sz>DefaultSize?sz:DefaultSize; heap = new Type[capacity]; size = 0; } MinHeap(Type ar[],int n) { capacity = n>DefaultSize?n:DefaultSize; heap = new Type[capacity]; for(int i=0; i<n; ++i) { heap[i] = ar[i]; } size = n; int pos = n/2-1; while(pos >= 0) { SiftDown(pos,n-1); pos--; } } ~MinHeap() { delete []heap; heap = NULL; } void Show()const { for(int i=0; i<size; ++i) { cout<<heap[i]<<" "; } cout<<endl; } bool IsEmpty()const { return size == 0; } bool IsFull()const { return size >= capacity; } void MakeHeap() { size = 0; } Type ReMoveMin() { Type tmp = heap[0]; heap[0] = heap[size-1]; size--; SiftDown(0,size-1); return tmp; } void Sort() { Type *data = new Type[size]; int i = 0; while(!IsEmpty()) { data[i++] = ReMoveMin(); } size = i; for(i=0; i<size; ++i) { heap[i] = data[i]; } delete []data; data = NULL; } void Insert(const Type &x) { heap[size] = x; SiftUp(size); size++; } private: void SiftUp(int start) { int j = start; int i = (j-1)/2; Type tmp = heap[j]; while(j>0) { if(tmp > heap[i]) break; else { heap[j] = heap[i]; j = i; i = (j-1)/2; } } heap[j] = tmp; } void SiftDown(int start,int end) { int i = start; int j = 2*i+1; Type temp = heap[i]; while(j <= end) { if(j<end && heap[j] > heap[j+1]) j = j+1; if(temp < heap[j]) break; else { heap[i] = heap[j]; i = j; j = 2*i+1; } } heap[i] = temp; } private: enum{DefaultSize = 10}; Type *heap; int capacity; int size; }; 堆可以被看作是一个完全二叉树,小堆排序利用小根堆堆顶记录的关键字最小这一个特征,使得从当前无序区中选取最小关键字并进一步记录操作变的简单。 以上内容由PHP站长网【52php.cn】收集整理供大家参考研究 如果以上内容对您有帮助,欢迎收藏、点赞、推荐、分享。 (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |