为防止广告，目前nocow只有登录用户能够创建新页面。如要创建页面请先登录/注册（新用户需要等待1个小时才能正常使用该功能）。
二叉堆/C++
来自NOCOW
< 二叉堆
C++非STL大根堆、小根堆实现：
//By Stanso #include <iostream> using namespace std; #define MAX_LONG 2147483647 class binary_heap { protected: long cnt; long h[100000]; binary_heap() {cnt=0;h[0]=0;}//其实h[0]没用 long pre(long n) {return n>>1;} long lch(long n) {return n<<1;} long rch(long n) {return (n<<1)+1;} public: long size(){return cnt;} }; class maxheap:public binary_heap { public: void ins(long n) { int p=++cnt;//元素个数+1，p指向堆底 while(p>1 && n>h[pre(p)])//若没到堆顶 且 待插入元素大于p的父亲 { h[p]=h[pre(p)];//则把p的父亲移到他儿子的地方(就是p的地方) p=pre(p);//p指向它的父亲 } h[p]=n;//最后把待插入元素放入p的地方 } long pop() { if(cnt==0) return -MAX_LONG;//返回-MAX_LONG视为错误 long p=1; long ans=h[1]; long tmp=h[cnt--];//取出堆底元素然 long to; while(p<=cnt)//若未到栈底 { to=-MAX_LONG;//init if(lch(p)<=cnt && tmp<h[lch(p)])//若有左孩子且比取出的栈底元素大 to=lch(p); if(rch(p)<=cnt && tmp<h[rch(p)] && h[to]<h[rch(p)])//若有右孩子 且 比取出的栈底元素大 且 大于左孩子 to=rch(p); if(to!=-MAX_LONG) {h[p]=h[to];p=to;}//如果比左右孩子都大，就说明找对位置了，把取出的栈底放上去；否则交换 else{h[p]=tmp;break;} } return ans; } }; class minheap:public binary_heap { public: void ins(long n) { int p=++cnt;//元素个数+1，p指向堆底 while(p>1 && n<h[pre(p)])//若没到堆顶 且 待插入元素小于p的父亲 { h[p]=h[pre(p)];//则把p的父亲移到他儿子的地方(就是p的地方) p=pre(p);//p指向它的父亲 } h[p]=n;//最后把待插入元素放入p的地方 } long pop() { if(cnt==0) return -MAX_LONG;//返回-MAX_LONG视为错误 long p=1; long ans=h[1]; long tmp=h[cnt--];//取出堆底元素然 long to; while(p<=cnt)//若未到栈底 { to=-MAX_LONG;//init if(lch(p)<=cnt && tmp>h[lch(p)])//若有左孩子且比取出的栈底元素小 to=lch(p); if(rch(p)<=cnt && tmp>h[rch(p)] && h[to]>h[rch(p)])//若有右孩子 且 比取出的栈底元素小 且 小于左孩子 to=rch(p); if(to!=-MAX_LONG) {h[p]=h[to];p=to;}//如果比左右孩子都小，就说明找对位置了，把取出的栈底放上去；否则交换 else{h[p]=tmp;break;} } return ans; } }; minheap h1; int main() { long tmp; while(cin >>tmp) h1.ins(tmp); cout <<endl<<"SIZE:"<<h1.size()<<endl<<endl; for(long i=h1.size();i>0;i--) cout <<h1.pop()<<endl; system("pause"); }
下面是C++模板实现堆排序：
#include<iostream> #include<vector> using namespace std; namespace Heap { template <class T> class BinaryHeap { vector<T> h; int n; public: BinaryHeap(); BinaryHeap(const T &err); void max_heapify(int i); void min_heapify(int i); void insert(const T &e); T minnum() const; T extract_min(); void decrease_key(int x,const T &k); void kill(int x); }; template<class T> BinaryHeap<T> heap_union(const BinaryHeap<T> &h1,const BinaryHeap<T> &h2); } template<class T> Heap::BinaryHeap<T>::BinaryHeap() { h.push_back(T ()); n=1; } template<class T> Heap::BinaryHeap<T>::BinaryHeap(const T &err) { h.push_back(err); n=1; } template<class T> void Heap::BinaryHeap<T>::max_heapify(int i) { for(;i>1;) { int p=i>>1; if(h[i]<h[p]) { T temp(h[i]); h[i]=h[p]; h[p]=temp; i=p; } else break; } } template<class T> void Heap::BinaryHeap<T>::min_heapify(int i) { if(i<1 ||i>=n) return; for(;;) { int left=i<<1; int right=left+1; int smallest; if(left>=n) break; if(right>=n) smallest=left; else { if(h[left]<h[right]) smallest=left; else smallest=right; } if(h[smallest]<h[i]) { T temp(h[i]); h[i]=h[smallest]; h[smallest]=temp; i=smallest; } else break; } } template<class T> void Heap::BinaryHeap<T>::insert(const T &e) { if(n>=h.size()) h.push_back(e); else h[n]=e; n++; max_heapify(n-1); } template<class T> T Heap::BinaryHeap<T>::minnum() const { if(n>1) return h[1]; return h[0]; } template<class T> void Heap::BinaryHeap<T>::decrease_key(int x,const T &k) { if(h[x]<k) return; h[x]=k; max_heapify(x); } template<class T> void Heap::BinaryHeap<T>::kill(int x) { if(x>=1 && x<n) { h[x]=h[n-1]; min_heapify(x); n--; } } template<class T> T Heap::BinaryHeap<T>::extract_min() { if(n>1) { T min=h[1]; kill(1); return min; } return h[0]; } int main() { int a[]={12,3,2,43,54,32,154,21,1}; int n=sizeof(a)/sizeof(int),i; Heap::BinaryHeap<int> bh; for(i=0;i<n;++i) bh.insert(a[i]); for(i=0;i<n;++i) cout<<bh.extract_min()<<' '; cout<<endl; return 0; }
---By D.puppet
