当前位置: 代码迷 >> 综合 >> STL源码剖析(四)heap--priority_queue
  详细解决方案

STL源码剖析(四)heap--priority_queue

热度:5   发布时间:2023-12-27 07:46:40.0

文章目录

  • 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:
  1. 采用list:当元素插入操作达到常数时间,但取值却需要对整个list进行扫描;将list先排序,使得list由大到小,这样取值与删除可达到最高效率,但元素插入却只有线性表现,不能两者兼得
  2. 采用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()处

  1. push_heap算法:上溯
    在这里插入图片描述
  • percolate up(上溯)程序:将新节点拿来与其父节点比较,如果其键值比父节点大,就父子对换位置,如此一直上溯,直到不需要对换或直到根节点为止

  • 当push_heap被调用时,新元素应已置于底部容器的最尾端

  • 具体push_heap实现参考源码

  1. pop_heap算法:下溯+上溯
    在这里插入图片描述
  • percolate_down(下溯)程序:将空间节点和其较大子节点“对调”并持续下放,直至叶节点为止,然后将前述被割舍的元素值设给空洞节点,然后再执行一次“上溯”程序
  • 在pop_heap时,除了将最大元素取出之外,还需调用__adjust_heap进行堆调整
  • 当调用完pop_heap时,最大元素只是被放置于底部容器的最尾端,尚未被取走,若要取其值,则需调用back(),若要删除,则需调用pop_back()
  • 具体pop_heap实现参考源码
  1. sort_heap算法
    在这里插入图片描述
  • sort_heap,就是对pop_heap的重复调用:
template <class RandomAccessIterator>
void sort_heap(RandomAccessIterator first, RandomAccessIterator last)
{
    while (last - first > 1 )pop_heap(first, last--);
}
  1. 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());}};
  相关解决方案