堆实现的优先队列模板

《堆实现的优先队列模板》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、堆实现的优先队列模板Postedon 2010-12-2321:25 ￥忘%风 阅读(1308)评论(0) 编辑 收藏 下面是自己手写的优先队列模板（默认是大顶堆，可通过重载小于号改变）用法说明如下:1）priority_queue部分（用法参照stl）c-free库函数帮助里提供的priority_queue用法说明如下：C++优先队列类似队列，但是在这个数据结构中的元素按照一定的断言排列有序。empty()如果优先队列为空，则返回真pop()删除第一个元素push()加入一个元素size()返回优先队列中拥有的元素

2、的个数top()返回优先队列中有最高优先级的元素2）堆的基本堆操作部分。用法如下：set_size()设置堆的大小set_value()设置堆中第id个元素的值creat_heap()创建一个初始堆heap_sort()堆排序，默认从小到大排，可通过重载小于号实现按指定规则排序is_heap()判断是否构成一个堆模板如下：?#defineMAXN25500typedef struct RedType{    int left,right;    int weight;    bool friend operator<(

3、const RedType&a,const RedType&b){        return a.weight>b.weight;    }}Edge;     class priority_queue{private :    RedTyper[MAXN];    int length;         void heap_adjust(int s,int m){        RedTyperc=r[s];        for (int j=s<<1;j<=m;j<<=1){            if (j<

4、m&&r[j]

5、h>>1;i>0;i--){            heap_adjust(i,length);        }    }         void set_size(int length){        this->length=length;    }         void set_value(int id,RedTypevalue){        r[id]=value;    }         void heap_sort(){        for (int i=length;i>1;i--){ 

6、           RedTypetmp=r[1];            r[1]=r[i];            r[i]=tmp;            heap_adjust(1,i-1);        }    }         bool is_heap(){        int len=length>>1-1,j;        if (len<1){            if (length==1

7、

8、(!(r[1]

9、-1])))                return true;            return false;        }        for (int i=1;i<=len;i++){            j=i<<1;            if (r[j]

10、riority_queue）==*/     void push(RedTyperc){        ++length;        r[length]=rc;        int s=length>>1;        for (int j=length;j>1;j>>=1){            if (!(r[s]<