【STL源码剖析】第四章 序列式容器 之 heap和priority_queue底层实现

本文主要是介绍【STL源码剖析】第四章 序列式容器 之 heap和priority_queue底层实现，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

heap

heap概述

heap并不归属于STL容器组件，它扮演priority queue的助手。binary max heap是priority queue的底层机制。

binary heap是一种complete binary tree（完全二叉树），也就是说，整棵binary tree除了最底层的叶节点(s)之外，是填满的，而最底层的叶节点(s)由左至右不得由空隙。

complete binary tree整棵树内没有任何节点漏洞。利用array来存储completebinary tree的所有节点，将array的#0元素保留，那么当complete binary tree的某个节点位于array的i处时，其左子节点必位于array的2i处，右子节点必位于array的2i+1处，父节点必位于i/2处。

根据元素排列方式，heap分为max-heap和min-heap两种，前者每个节点的键值都大于或等于其子节点的值，后者每个节点的键值都小于或等于其子节点的值。max-heap中最大值在根节点，min-heap最小值在根节点。底层存储结构为vector或者array。

heap算法

push_heap算法

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

新元素是否适合于其现有位置呢？为满足max-heap的条件（每个节点的键值都大于或等于其子节点键值），我们执行一个所谓的percolate up（上溯）程序：将新节点拿来与其父节点比较，如果其键值（key）比父节点大，就父子对换位置，如此一直上溯，直到不需对换或直到根节点为止。

  template<class RandomAccessIterator>inline void push_heap(RandomAccessIterator first,RandomAccessIterator last){    //注意，此函数被调用时，新元素应已置于底部容器的最尾端    _push_heap_aux(first,last,distance_type(first),value_type(first))；}​template<class RandomAccessIterator，class Distance,class T>inline void _push_heap_aux(RandomAccessIterator first,Distance*,T*){    _push_heap(first,Distance(last-first)-1),Distance(0),T(*(last-1)));    //以上系根据implicit representation heap的结构特性：新值必须置于底部容器的最尾端，此即第一个洞号：（last-first）-1}​template<class RandomAccessIterator，class Distance,class T>void _push_heap(RandomAccessIterator first,Distance holeIndex,Distance topIndex,T value){    Distance parent(holeIndex-1)/2;//找出父节点    while(holeIndex>topIndex&&*(first

这篇关于【STL源码剖析】第四章 序列式容器 之 heap和priority_queue底层实现的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---