算法學(xué)習(xí)
C++ 及算法

最小堆的實現(xiàn)(c++模板)

#define MAXN 10000

template<typename Type>

class Heap{

private:

int size;

Type data[MAXN+1];

void siftdown( int pos );

public:

Heap();

void push( Type key );

Type pop();

void make_heap();

bool empty();

void clear();

int get_size();

};

template<typename Type>

Heap<Type>::Heap(){

size= 0; }

template<typename Type>

int Heap<Type>::get_size(){

return size; }

template<typename Type>

bool Heap<Type>::empty(){

return size== 0;}

template<typename Type>

void Heap<Type>::clear(){

size= 0; }

template<typename Type>

void Heap<Type>::siftdown( int pos ){

while( pos<<1<= size ){

int t= pos<<1;

if( (pos<<1)+ 1<= size && data[(pos<<1)+1]<data[t] ) t= (pos<<1)+ 1;

if( data[t]< data[pos] ){

Type tmp= data[t]; data[t]= data[pos]; data[pos]= tmp;

pos= t; }

else break;

}

template<typename Type>

void Heap<Type>::push( Type key ){

data[++size]= key;

int pos= size;

while( pos> 1 ){

if( data[pos>>1]> data[pos] ){

Type tmp= data[pos];

data[pos]= data[pos>>1]; data[pos>>1]= tmp;

pos>>= 1; }

else break;

}

template<typename Type>

Type Heap<Type>::pop(){

Type tmp= data[1]; data[1]= data[size];

data[size]= tmp; size--;

siftdown(1); return data[size+1];

}

posted on 2009-04-16 18:31 Darren 閱讀(4367) 評論(4) 編輯收藏引用

評論:

# re: 最小堆的實現(xiàn)(c++模板) 2009-04-16 22:57 | 打醬油

傳說中的手寫堆？Orz。。。回復(fù) 更多評論

# re: 最小堆的實現(xiàn)(c++模板) 2009-04-17 16:57 | brightcoder

void make_heap()定義哪去了？回復(fù) 更多評論

# re: 最小堆的實現(xiàn)(c++模板) 2009-04-17 17:04 | Darren

@brightcoder
那個應(yīng)該很好寫了，循環(huán)一次就行了。
本來是要寫的，不過發(fā)現(xiàn)一次次插入就能建堆了。
回復(fù) 更多評論

# re: 最小堆的實現(xiàn)(c++模板) 2009-05-17 16:55 | myo1olove

高人！！！
太敬佩你了，我已‘偷借’你好幾篇代碼了！！！
thank you 回復(fù) 更多評論

刷新評論列表

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



網(wǎng)站導(dǎo)航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

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

留言簿(5)

隨筆分類

ACMers

搜索

積分與排名

最新隨筆

最新評論