STL中priority_queue与multiset的区别：
以降序为例：两者都是可以快速O(1)获得最小元素，但是在建立的过程却有差异，priority_queue需要O(n),而multiset是需要O(nlogn)的。因为priority_queue是通过堆来实现，是需要上方小于下方元素便可，而multiset则是通过AVL树来实现，需要满足二叉排序树的规则。
插入/删除元素时：都是O(logn),但是由于AVL树需要调整等，故而会比priority_queue的O(logn)大一些。获得最小数则同是O(1)
差别：
multiset中需要较多内存去储存结点间的指针，但是优先队列则不用。
优先队列不能访问除队首元素之外的其他元素。而multiset则可以使用迭代器访问，同时整个序列都是有序的。set可以支持find操作，返回该位置迭代器。
单调队列：以降序为例：通过双向队列实现，由队尾进入，如果队尾元素小于当前元素，则队尾元素弹出，直到队尾元素大于当前元素才入队。单调队列相比于优先队列的优势是在于其可以按照原来序列的元素位置来排列当前队列中的最大值，而不是直接打乱顺序获得最大值。
网友评论