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

堆实现的优先队列模板 Posted on?2010-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 25500 typedef?struct?RedType { ????int?left, right; ????int?weight; ????bool?friend?operator (const?RedType a, const?RedType b) { ????????return?a.weight b.weight; ????} }Edge; ????? class?priority_queue { private?: ????RedType r[MAXN]; ????int?length; ????? ????void?heap_adjust(int?s, int?m) { ????????RedType rc = r[s]; ????????for?(int?j = s 1; j = m; j = 1) { ????????????if?(j m r[j] r[j+1]) j++; ????????????if?(!(rc r[j])) break; ????????????r[s] = r[j]; s = j; ????????} ????????r[s] = rc; ????} ????? public?: ????priority_queue() { ????????length = 0; ????} ????/*===========下面是堆操作部分，建堆，堆排等=============*/ ????? ????void?creat_heap() { ????????for?(int?i = length 1; i 0; i--) { ????????????heap_adjust(i, length); ????????} ????} ????? ????void?set_size(int?length) { ????????this-length = length; ????} ????? ????void?set_value(int?id, RedType value) { ????????r[id] = value; ????} ????? ????void?heap_sort() { ????????for?(int?i = length; i 1; i--) { ????????????RedType tmp = 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 || (!(r[1] r[length]) ???????????? !(r[1] r[length - 1]))) ????????????????return?true; ????????????return?false; ????????} ????????for?(int?i = 1; i = len; i++) { ????????????j = i 1; ????????????if?(r[j] r[j + 1]) j++; ????????????if?(r[i] r[j]) return?false; ????????} ????????return?true;