堆实现的优先队列模板.doc

堆实现的优先队列模板Posted on2010-12-23 21:25￥忘%风阅读(1308) 评论(0)编辑收藏下面是自己手写的优先队列模板（默认是大顶堆，可通过重载小于号改变）用法说明如下:1）priority_queue部分（用法参照stl）c-free库函数帮助里提供的priority_queue用法说明如下：C+优先队列类似队列，但是在这个数据结构中的元素按照一定的断言排列有序。empty()如果优先队列为空，则返回真pop()删除第一个元素push()加入一个元素size()返回优先队列中拥有的元素的个数top()返回优先队列中有最高优先级的元素2）堆的基本堆操作部分。用法如下：set_size()设置堆的大小set_value()设置堆中第id个元素的值creat_heap()创建一个初始堆heap_sort()堆排序，默认从小到大排，可通过重载小于号实现按指定规则排序is_heap()判断是否构成一个堆模板如下：?#define MAXN 25500typedefstructRedType intleft, right;intweight;boolfriendoperator b.weight;Edge;classpriority_queue private:RedType rMAXN;intlength;voidheap_adjust(ints, intm) RedType rc = rs;for(intj = s 1; j = m; j = 1) if(j m & rj rj+1) j+;if(!(rc 1; i 0; i-) heap_adjust(i, length);voidset_size(intlength) this-length = length;voidset_value(intid, RedType value) rid = value;voidheap_sort() for(inti = length; i 1; i-) RedType tmp = r1;r1 = ri;ri = tmp;heap_adjust(1, i - 1);boolis_heap() intlen = length 1 - 1, j;if(len 1) if(length = 1 | (!(r1 rlength) & !(r1 rlength - 1)returntrue;returnfalse;for(inti = 1; i = len; i+) j = i 1;if(rj rj + 1) j+;if(ri 1;for(intj = length; j 1; j = 1) if(!(rs = 1;voidpop() RedType tmp = r1;r1 = rlength;rlength = tmp;heap_adjust(1, -length);RedType top() returnr1; intsize() returnlength;boolempty() if(length 根节点不断做heap_adjust()，使之构成一个初始堆。-n / 2 * log(n)heap_sort() 相当于重复n次pop()操作，但length不改变。-n * log(n)is_heap() 判断是否构成堆，堆大小小于4时由外面的if判定，避免for