The Fourth Dimension Space

枯葉北風寒，忽然年以殘，念往昔，語默心酸。二十光陰無一物，韶光賤，寐難安；不畏形影單，道途阻且慢，哪曲折，如渡飛湍。斬浪劈波酬壯志，同把酒，共言歡！ -如夢令

統計

隨筆 - 414
文章 - 13
評論 - 521
引用 - 0

常用鏈接

留言簿(16)

隨筆檔案

文章檔案

Blogs in Computer Vision and Algorithm

CMU CV Group

友情鏈接

n皇后問題精彩分析
RMQ問題的精彩文章
開關燈問題

搜索

閱讀排行榜

評論排行榜

最小堆類

#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;

}

一個自實現的優先隊列最小堆。

#include<iostream>

#include<cmath>

#include<algorithm>

using namespace std;

template<class T>

class MinHeap

{

public:

T *heap;

int CurrentSize;

int MaxSize;

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

void FilterUp(int start);

public:

MinHeap(int n);

~MinHeap(){delete []heap;}

bool Insert(const T &x);

T RemoveMin();

T GetMin();

};

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+1]<heap[j])

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)>>1;

}

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];

}

稍微改良一下啊只需要重載<符號即可

posted on 2009-05-08 16:57 abilitytao 閱讀(424) 評論(0) 編輯收藏引用

只有注冊用戶登錄后才能發表評論。




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

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

The Fourth Dimension Space

導航

統計

常用鏈接

留言簿(16)

隨筆檔案

文章檔案

Blogs in Computer Vision and Algorithm

友情鏈接

搜索

最新評論

閱讀排行榜

評論排行榜

最小堆類