STL源码剖析（四）heap--priority_queue_综合

文章目录

1. heap概述
2. 为何选择heap作为priority queue的底层机制？
3. binary heap
4. heap算法
5. priority_queue

1. heap概述

heap,即我们在数据结构中所说的堆；在STL中我们所应用到priority queue中作为其操作实现的是binary max heap（最大二叉堆），是一种complete binary tree（完全二叉树）

heap可分为max-heap以及min-heap，而在此文中所要介绍的是max-heap，所谓max-heap，即每个节点的键值都大于或等于其子节点键值，其最大值在根节点，总是位于底层array或vector的首部

2. 为何选择heap作为priority queue的底层机制？

首先了解priority queue，允许用户以任何次序将任何元素推入容器内，但取出时一定是从优先权最高的元素开始取
下面我们来分析一下为何采用heap：

采用list：当元素插入操作达到常数时间，但取值却需要对整个list进行扫描；将list先排序，使得list由大到小，这样取值与删除可达到最高效率，但元素插入却只有线性表现，不能两者兼得
采用binary search tree：元素的插入与取值可达到O(logN)，但未免小题大做，况且binary search tree的输入需要足够的随机性，而且binary search tree并不容易实现

结合上述，又能满足priority queue的条件，又能达到高效率，binary heap就这样作为了其底层实现

3. binary heap

binary heap就是一种complete binary tree，而complete binary tree又是什么结构呢？

在这里插入图片描述

complete binary tree 整棵树内没有任何节点漏洞，这带来一个极大的好处：我们可以利用array来存储所有节点。假设动用一个小技巧，将array的#0元素保留（或设为无限大或无限小），那么当complete binary tree中的某个节点位于array的i处时，其左子节点必位于array的2i处，其右子节点比位于array的2i+1处，其父节点必位于“i/2”处。通过这么简单的位置规则，array可以轻易实现出complete binary tree。这种以array表述tree的方式，我们称为隐式表述法。
这么一来，我们需要的工具就很简单了：一个array 和一组 heap算法（用来进行元素操作，并将某一整组数据排列成一个heap）。array的缺点是无法动态改变大小，而heap却需要这项功能，因此，以vector代替array是更好的选择。

4. heap算法

为了满足complete binary tree的条件，新加入的元素一定要放在最下一层作为叶节点，并填补在由左至右的第一个空格，也就是把新元素插入在顶层vector的end()处

push_heap算法：上溯

percolate up（上溯）程序：将新节点拿来与其父节点比较，如果其键值比父节点大，就父子对换位置，如此一直上溯，直到不需要对换或直到根节点为止
当push_heap被调用时，新元素应已置于底部容器的最尾端
具体push_heap实现参考源码

pop_heap算法：下溯+上溯

percolate_down（下溯）程序：将空间节点和其较大子节点“对调”并持续下放，直至叶节点为止，然后将前述被割舍的元素值设给空洞节点，然后再执行一次“上溯”程序
在pop_heap时，除了将最大元素取出之外，还需调用__adjust_heap进行堆调整
当调用完pop_heap时，最大元素只是被放置于底部容器的最尾端，尚未被取走,若要取其值，则需调用back()，若要删除，则需调用pop_back()
具体pop_heap实现参考源码

sort_heap算法

sort_heap，就是对pop_heap的重复调用:

template <class RandomAccessIterator>
void sort_heap(RandomAccessIterator first, RandomAccessIterator last)
{
    while (last - first > 1 )pop_heap(first, last--);
}

make_heap算法

这个算法用来将一段现有数据转换为一个heap
make_heap实现参考源码

5. priority_queue

priority_queue是一个容器适配器（与stack、queue一样），以vector作为其底层结构，以heap算法作为其操作实现

priority_queue实现：

template <class T, class Sequence = vector<T>,class Compare = less<typename Sequence::value_type> >
class priority_queue {
    
public://vector自定义类型
protected:Sequence c;        //底层容器Compare comp; //元素大小比较标准
public：//...//用到heap泛型算法作为其实现//定义一个priority_queue实则是一个建堆的过程template <class InputIterator>priority_queue( InputIterator first,  InputIterator last, const Compare& x): c (first, last), comp(x) {
     make_heap(c.begin(), c.end(), comp);}priority_queue( InputIterator first,  InputIterator last): c (first, last) {
     make_heap(c.begin(), c.end(), comp);}//....void push(const value_type& x)  {
    __STL_TRY {
    //先利用底层容器的 push_back将新元素推入末端，再重排heapc.push_back(x);push_heap(c.begin(), c.end(), comp);}__STL_UNWIND(c.clear());}void pop()  {
    __STL_TRY {
    //先从heap内取出一个元素，并不是简单的弹出，而是重排heap，然后在以底层容器的pop_back取得被弹出的元素pop_heap(c.begin(), c.end(), comp);c.pop_back();}__STL_UNWIND(c.clear());}};