存档

文章标签 ‘优先队列’

STL笔记之优先队列

2014年7月5日 2 条评论

在STL中队列queue是基于deque实现的,优先队列priority_queue则是基于堆实现的。所谓优先队列即元素具有优先级的队列,在最大优先级队列中,队列最前面的元素具有最高的优先级,最大优先级队列基于最大堆(max-heap)实现。
1. 堆的基本性质
二叉堆是一颗完全二叉树,可以分为最小堆和最大堆,以最大堆为例来说,对于堆中的每一个节点p,都满足条件key[p] >= key[p->left] && key[p] >= key[p->right],即以p为根的子树中,根节[......]

继续阅读

POJ 1521 Entropy[哈弗曼编码]

2011年9月3日 2 条评论

题目大意:题目很长,不过就是哈弗曼编码。
解题思路:还是用优先队列(STL提供了priority_queue)来做,先构建好哈弗曼树,然后求每个叶节点的深度就好了。这里用数据来构建哈夫曼树,方便。
传送门:POJ 1521 Entropy http://poj.org/problem?id=1521
Problem: 1521 Memory: 232K Time: 16MS Language: C++ Result: Accepted

#include <iostream>[......]

继续阅读

POJ 3253 Fence Repair[哈夫曼树]

2011年9月2日 没有评论

这个题就是一个哈弗曼树的问题,感觉对树的操作还是不太熟悉,这里再次借用STL里面的优先队列priority_queue来解决问题了。
不过,在Visual Studio的Debug模式下运行时竟然遇到一个问题,提示一个错误“stack around the variable n was corrupted”,感觉有点奇怪,网上虽然有那种很临时的解决方案:“把 Project->配置属性->C/C++ ->代码生成->基本运行时检查为 默认值”就不会报出异常,不过个人感觉这种解决方案毫无意义,因为你还是不[......]

继续阅读

复数集合(优先队列)

2011年8月31日 没有评论

题目描述
一个复数(x+iy)集合,两种操作作用在该集合上:
1. Pop 表示读出集合中复数模值最大的那个复数,如集合为空输出empty,不为空就输出最大的那个复数并且从集合中删除那个复数,再输出集合的大小SIZE;
2. Insert a+ib 指令(a,b表示实部和虚部),将a+ib加入到集合中 ,输出集合的大小SIZE;
最开始要读入一个int n,表示接下来的n行每一行都是一条命令。
输入
输入有多组数据。
每组输入一个n(1小于等于n小于等于1000),然后再输入n条指[......]

继续阅读

分类: 其他题解 标签: , ,