priority_queue的底层结构为max heap(也可以是min heap,本文统一只叙述max heap),heap并不属于STL的容器组件.
heap是一颗完全二叉树:整颗树除了最底层,都是填满的,而且底层节点从左到右不存在空隙。
因此,heap通常用vector的方式存储:
heap的某个节点位于位置 i 时,其左右子节点分别位于2i 和 2i+1
Heap相关 *** 作 push_heap首先,因为要满足完全二叉树的性质,需要将新节点放置在底层节点的最后面,也就是vector的end(),然后执行上溯 *** 作:只要父节点比自己小,就不断调换自己和父节点的位置。
将heap的最大元素取走,也就是将根节点取走,那根据完全二叉树的性质,得把底层最后面的元素换到根节点。
然后不断执行下溯 *** 作:将自己和两个子节点中,较大的那个对调。
做完下溯 *** 作后,可能还需做一次上溯 *** 作
sort_heap:不断对heap进行pop *** 作,就可以得到一个有序序列。
priority_queue底层默认以vector做为容器,其自身归类为适配器。
priority_queue在两端 *** 作数据,没有提供迭代器,因此也不提供遍历功能。
其make_heap,push和pop参数有迭代器参数类型,是针对vector的迭代器哦。
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)