c++ set,map,priority_queue的底层数据结构比较以及思考_priority queue与set

问题来源
一道算法题，给定m次操作，可以是插入一个随机数据，可以是删除一个最小的数据，可以是输出展示一个最小的数据。

开始我是用的最基础的vector去做的，但是问题在于，每一次插入数据后需要重新排序，导致算法的时间复杂度很高，于是想到使用set数据结构，因为set是自动插入数据后从小到大排序的。
但是两个问题，第一是题目中可能会有重复数据，set会自动去重，会导致答案错误。
第二是仍然超时严重，只能过40%的测试案例

于是改换成优先队列priority_queue 完美通过

所以，引发一个思考，为什么priority_queue和set都是自动排序，但是时间复杂度相差很大。查询资料发现，set的实现数据结构是红黑树，而优先队列的实现数据结构是完全二叉树形式的堆。两者严格意义上都是二叉树的基础数据结构，而且都需要维持树的平衡。


红黑树笔者没有理解清除其具体的实现机理，但是***两者都需要在插入数据之后，再次调整树的结构，以实现平衡***。单从查询角度看，两者的效率是相同的，但是插入之后的调整树的方式，决定了时间复杂度的不同。（map的实现也是红黑树）

上述图片中，可以看到对于优先队列，插入数据是在最尾端，然后进行调整，并且数据可以被存放在数组中，

不得不承认，在降低时间复杂度上，优先队列非常的出色。