国产偷久久久精品专区,欧美久久综合九色综合,久久精品国产亚洲综合色

最小堆類

#include<iostream>

#include<cmath>

#include<algorithm>

using namespace std;

template<class T>

class MinHeap

{

private:

T *heap;

int CurrentSize;

int MaxSize;

void FilterDown(const int start,const int end);

void FilterUp(int start);

public:

MinHeap(int n);

MinHeap();

~MinHeap(){delete []heap;}

bool Insert(const T &x);

T RemoveMin();

T GetMin();

bool IsEmpty() const{return CurrentSize==0;}

bool IsFull() const{return CurrentSize==MaxSize;}

void Clear(){CurrentSize=0;}

};

template<class T>

MinHeap<T>::MinHeap()

{

MaxSize=1000;

heap=new T[MaxSize];

CurrentSize=0;

}

template<class T>

MinHeap<T>::MinHeap(int n)

{

MaxSize=n;

heap=new T[MaxSize];

CurrentSize=0;

}

template<class T>

void MinHeap<T>::FilterDown(const int start,const int end)

{

int i=start,j=2*i+1;

T temp=heap[i];

while(j<=end)

{

if(j<end&&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>

bool MinHeap<T>::Insert(const T &x)

{

if(CurrentSize==MaxSize)

return false;

heap[CurrentSize]=x;

FilterUp(CurrentSize);

CurrentSize++;

return true;

}

template<class T>

void MinHeap<T>::FilterUp(int start)

{

int j=start,i=(j-1)/2;

T temp=heap[j];

while(j>0)

{

if(heap[i]<=temp)break;

else

heap[j]=heap[i];j=i;i=(i-1)/2;

}

heap[j]=temp;

}

template<class T>

T MinHeap<T>::RemoveMin( )

{

T x=heap[0];

heap[0]=heap[CurrentSize-1];

CurrentSize--;

FilterDown(0,CurrentSize-1);

return x;

}

template<class T>

T MinHeap<T>::GetMin()

{

return heap[0];

}

int main ()

{

MinHeap<int> test(8);

int k;

bool tem;

for(k=1;k<=10;k++)

{

tem=test.Insert(10-k);

}

tem=test.IsEmpty();

tem=test.IsFull();

for(k=1;k<=5;k++)

test.RemoveMin();

return 0;

}

posted on 2009-07-14 16:24 abilitytao 閱讀(184) 評論(0) 編輯收藏引用

只有注冊用戶登錄后才能發表評論。
【推薦】100%開源！大型工業跨平臺軟件C++源碼提供，建模，組態！



網站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

The Fourth Dimension Space

導航

統計

常用鏈接

留言簿(16)

隨筆檔案

文章檔案

Blogs in Computer Vision and Algorithm

友情鏈接

搜索

最新評論

閱讀排行榜

評論排行榜

最小堆類