SGI STL 标准库 heap priority-queue 5

github源码分析仓库

heap 堆


heap允许用户以任意次序将任何元素推入容器内,但取出时一定是从优先权最高的元素开始取。
heap并不是STL容器组件,而是priority-queue的底层所使用的算法。而priority-queue底层缺省使用vector并搭配max-heap算法。根据元素排列方式heap分为max-heap和min-heap两种,max-heap每个节点的键值都大于或等于其子节点键值,min-heap每个节点的键值都小于或等于其子节点键值,因此max-heap最大值在根节点,min-heap最小值在根节点。STL提供max-heap。
可以使用数组表示一颗完全二叉树,然后将数组第0位保留,当对完全二叉树位于数组的i处时,其左节点位于数组的2*i处,其右子节点必位于数组的2*i+1处,其父节点位于i/2处。

1. push_heap

新加入的元素先放在最下层作为叶节点,因为是完全二叉树,所以一定放在最下层的最右边,即底层容器的end()处。
然后为了满足max-heap的条件,将这个新节点,和父节点做比较,如果其键值大于父节点,父子节点对换位置,一直向上,直到不需要对换或到根节点为止。
push_heap算法

2. pop_heap

取走最大值(根节点)的操作,先将根节点和最底层最右边的叶节点对调,然后从上到下,用根节点和其左右两个子节点比较,当根节点小于其中任意一个的时候,取最大的那个和根节点对调,根节点作为其子节点,然后该子节点,作为子树的根节点再次判断,重复该过程,直到叶子或其比左右叶子节点都大的时候停止。然后底层容器的end()即为max-heap的最大值。
pop_heap算法

3. sort_heap

堆排序,每次都取堆顶,放在底层容器的最后端,对整个堆做pop_heap操作,当堆为空时,便可得到递增排序好的序列。
sort_heap算法

4. make_heap

排列一段现有数据为max-heap, 先找到第一个需要重排的子树头部,排列其成为一个最大堆,指针前移,再排列该树为最大堆,直到走完整个需要重新排列的元素为止。

priority-queue 优先级队列


priority-queue是一个拥有权值概念的queue,允许加入新元素、移除旧元素、查看元素值等功能,由于是queue,所以只允许从底端加入,从顶端取出。
priority-queue其内部元素按照权值自动排序,权值高者在在前面。缺省情况下priority-queue利用max-heap完成。priority-queue没有迭代器。priority-queue的实现依靠底层容器的方法和heap的泛型算法。