关于优先列队 和 堆排序的一个疑问。
关于优先列队 和 堆排序的一个疑问。
优先队列 的出队是按照优先级的，优先级越高，越先出队。如果优先级相同。则先进先出。
一般情况下，优先列队的实现都是用 堆 实现的。好多书上都是这样讲的。
可是问题就来了。
用堆实现的优先列队，和 堆排序很像。但是 堆排序 又是不稳定的，那么那些用堆实现的 优先列队是如何保证 相同优先级的 先进先出的呢？ 优先列队?堆排序 优先列队?和?堆排序的一个疑问。 优先列队 堆排序
[解决办法]
不保证……STL的priority_queue用的heap就是不保证同优先级的FIFO的。
要想做到这点，最方便的方法是和把任何排序改成稳定的方法一样，key增加一个field表示原序列中的序号，并让它参与比较。
[解决办法]
优先队列不保证先进先出呀，不过稍微改一改，自己做一个编号，在值相同的情况下比较这个编号就好了。
[解决办法]
扩展个域不就行了
