STL源码剖析(四):容器(4)priority

STL源码剖析(四):容器(4)priority,第1张

Heap

priority_queue的底层结构为max heap(也可以是min heap,本文统一只叙述max heap),heap并不属于STL的容器组件.

heap是一颗完全二叉树:整颗树除了最底层,都是填满的,而且底层节点从左到右不存在空隙。


因此,heap通常用vector的方式存储:

heap的某个节点位于位置 i 时,其左右子节点分别位于2i 和 2i+1

Heap相关 *** 作 push_heap

首先,因为要满足完全二叉树的性质,需要将新节点放置在底层节点的最后面,也就是vector的end(),然后执行上溯 *** 作:只要父节点比自己小,就不断调换自己和父节点的位置。


pop_heap

将heap的最大元素取走,也就是将根节点取走,那根据完全二叉树的性质,得把底层最后面的元素换到根节点。


然后不断执行下溯 *** 作:将自己和两个子节点中,较大的那个对调。


做完下溯 *** 作后,可能还需做一次上溯 *** 作

 sort_heap:不断对heap进行pop *** 作,就可以得到一个有序序列。


priority_queue

priority_queue底层默认以vector做为容器,其自身归类为适配器。


priority_queue在两端 *** 作数据,没有提供迭代器,因此也不提供遍历功能。


其make_heap,push和pop参数有迭代器参数类型,是针对vector的迭代器哦。


欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/langs/569101.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-04-09
下一篇 2022-04-09

发表评论

登录后才能评论

评论列表(0条)

保存