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


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