学步园

#include <iostream><br /> #include <string><br /> #include <cassert><br /> #include <set><br /> #include <algorithm><br /> #include <windows.h><br /> #include <stack><br /> #include <vector><br /> #include <time.h><br /> #include <windows.h><br /> #include <fstream><br /> #include <string><br /> using namespace std;</p> <p>template<typename T><br /> class Heap<br /> {</p> <p>public:</p> <p> Heap(int capacity):size(0)<br /> {<br /> v.resize(1+capacity);<br /> v[0]=0;<br /> }</p> <p> const T& Top()<br /> {<br /> assert(!IsEmpty());<br /> return v[1];<br /> }</p> <p> void Push(const T& val)<br /> {<br /> size++;<br /> v[size]=val;<br /> SiftUp(size);<br /> }</p> <p> void Pop()<br /> {<br /> assert(!IsEmpty());<br /> swap(v[1],v[size]);<br /> size--;<br /> //**************<br /> if (!IsEmpty())<br /> {<br /> SiftDown(1);<br /> }<br /> //**************<br /> }</p> <p> bool IsEmpty()<br /> {<br /> return size == 0;<br /> }</p> <p>private:</p> <p> void SiftUp(int index)<br /> {<br /> assert(index >= 1 && index <= size);<br /> int i=index;<br /> while(i/2 !=0 && Pred(v[i],v[i/2]))<br /> {<br /> assert(i >= 1 && i <= size);<br /> swap(v[i],v[i/2]);<br /> i/=2;<br /> }<br /> }</p> <p> void SiftDown(int index)<br /> {<br /> assert(index >= 1 && index <= size);<br /> int lchild=2*index;<br /> int rchild=lchild+1;<br /> int i=index;<br /> if (lchild <= size && Pred(v[lchild],v[i]))<br /> {<br /> i=lchild;<br /> }<br /> if (rchild <= size && Pred(v[rchild],v[i]))<br /> {<br /> i=rchild;<br /> }<br /> assert(i >= 1 && i <= size);<br /> if (i != index)<br /> {<br /> swap(v[index],v[i]);<br /> SiftDown(i);<br /> }<br /> }</p> <p> bool Pred(const T& left,const T& right)<br /> {<br /> return left > right;<br /> }<br /> private:</p> <p> int size;<br /> //start from 1<br /> vector<T> v;<br /> };</p> <p>int main ()<br /> {<br /> //<br /> srand(time(0));<br /> //<br /> vector<int> vi;<br /> Heap<int> h(100);<br /> for (int i=0;i<100;i++)<br /> {<br /> int r=rand();<br /> h.Push(r);<br /> cout << r << '/t';<br /> vi.push_back(r);<br /> }<br /> cout << endl;<br /> int v=h.Top();<br /> h.Pop();<br /> while(!h.IsEmpty())<br /> {<br /> cout << v << '/t';<br /> int temp=h.Top();<br /> h.Pop();<br /> assert(temp <= v);<br /> v=temp;<br /> }<br /> cout << v << '/t';<br /> cout << endl;<br /> //<br /> sort(vi.begin(),vi.end(),greater<int>());<br /> for (int i=0;i<vi.size();i++)<br /> {<br /> cout << vi[i] << '/t';<br /> }<br /> //<br /> system("pause");<br /> return 0;<br /> }<br />