The Fourth Dimension Space

枯叶北风寒,忽然年以残,念往昔,语默心酸。二十光阴无一物,韶光贱,寐难安; 不畏形影单,道途阻且慢,哪曲折,如渡飞湍。斩浪劈波酬壮志,同把酒,共言欢! -如梦令

最小堆类

#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 阅读(394) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理