C++ STL容器(五) —— priority_queue 底层剖析

news/2024/10/9 0:30:05 标签: c++, java, 数据结构, 堆, STL, 大根堆, 小根堆

这篇来讲下 priority_queue，其属于 STL 的容器适配器，容器适配器是在已有容器的基础上修改活泼限制某些数据接口以适应更特定的需求，比如 stack 栈使数据满足后进先出，queue 队列使数据满足先进先出，其都是在已有容器上进行适配，以满足更细的需求。

文章目录

  • 堆的简单介绍
  • UML 类图
  • 代码解析
    • 构造函数
    • 插入元素
    • 删除元素

堆的简单介绍

堆是一棵二叉树，且是一棵完全二叉树，对于大根堆，根节点是这棵二叉树中最大的元素，也可以说每一棵子树的根节点都是这棵子树的最大元素，那么父节点一定是比左右孩子以及后代节点都大的。而小根堆，则是相反，根节点是这棵二叉树中最小的元素。

比如下图中左边是大根堆，而右边是小根堆。

堆的初始化

那么对于一个数组(随机排列的/随机生成的)，我们要怎么把它转换大根堆/小根堆呢。

比如对于上图中的序列，可能初始序列是下图这样的。

那么根据这个初始序列将其转换成大根堆，可以采用从下至上的方式，先从右下角的子树开始调整，这个子树的根节点是 12 比它的孩子 1 大，所以不需要进行调整。

那么再调整左下角的子树，这个子树根节点是 3 比它的两个孩子都要小，那么和其最大的儿子交换，即 9，之后看交换完后，以 3 为根节点的子树是否还需要继续调整，而此时 3 已经是叶子节点了，没有左右孩子，所以不需要继续调整了，这轮调整结束。

然后再调整最上面的子树，8 为根节点，其比两个孩子节点要小，和其中最大的孩子交换，即 12，交换完后，其比孩子 1 小，所以不需要继续调整，本轮调整结束。

堆的插入

堆的插入操作，就是先插入到完全二叉树的下一个叶子节点，然后自下而上进行调整，而这个调整与堆初始化操作不一样的地方在于，如果父节点下沉了(即父节点和子节点发生交换)，那么交换之后的下方子树不用再尝试进行调整了，因为当前父节点一定是这棵子树中的最大元素(大根堆)。

那么我们尝试在上面的大根堆中插入一个元素 14。

  1. 首先插入到完全二叉树的最后的叶子节点

  2. 调整以插入元素为儿子节点的子树

  3. 继续调整以 14 为儿子节点的子树，此时 14 已经是整棵大根堆的根节点了，不需要继续调整了。

堆的删除

堆的删除，是指把堆顶元素弹出， 通过把最末尾的叶子节点的元素放到根节点，然后删除最末的叶子节点，之后再从上至下进行调整即可。这里的调整与堆初始化操作的调整类似，如果根节点比两个孩子节点都大(大根堆)，则不需要继续调整了，否则与其中最大的孩子交换，再继续向下调整子树。

  1. 将末尾的叶子拿到根节点，然后删除该叶子
  2. 8 比左右孩子都小，找到最大的孩子 12 交换，下面的子树 8 比 1 大，所以不需要继续调整了

UML 类图

下面看下 MSVC 实现中的 UML 类图，这里的容器可以是 vector 也可以是 list 等其它容器，这些容器要实现一些方法，因为在 priority_queue 里会使用，默认提供的是 vector，而 _Pr 提供的是比较函数，可以是仿函数，也可以是一个函数指针，_Pr 要实现给定两个参数的比较，默认提供的是 less 仿函数。

代码解析

构造函数

构造函数比较简单，就是把给定容器和比较函数初始化了，然后调用 _Make_heap 初始化堆。

priority_queue() = default;

explicit priority_queue(const _Pr& _Pred) noexcept(
    is_nothrow_default_constructible_v<_Container>
    && is_nothrow_copy_constructible_v<value_compare>) // strengthened
    : c(), comp(_Pred) {}

priority_queue(const _Pr& _Pred, const _Container& _Cont) : c(_Cont), comp(_Pred) {
    _Make_heap();
}

priority_queue(const _Pr& _Pred, _Container&& _Cont) : c(_STD move(_Cont)), comp(_Pred) {
    _Make_heap();
}

template <class _InIt, enable_if_t<_Is_iterator_v<_InIt>, int> = 0>
priority_queue(_InIt _First, _InIt _Last, const _Pr& _Pred, const _Container& _Cont) : c(_Cont), comp(_Pred) {
    c.insert(c.end(), _First, _Last);
    _Make_heap();
}

下面看下 _Make_heap 的代码，调用了 make_heap 函数，首先检查提供的两个迭代器，然后 _Make_heap_unchecked 进行堆的初始化

    void _Make_heap() {
        _STD make_heap(c.begin(), c.end(), _STD _Pass_fn(comp));
    }

	_EXPORT_STD template <class _RanIt, class _Pr>
_CONSTEXPR20 void make_heap(_RanIt _First, _RanIt _Last, _Pr _Pred) { // make [_First, _Last) into a heap
    _STD _Adl_verify_range(_First, _Last);
    _STD _Make_heap_unchecked(_STD _Get_unwrapped(_First), _STD _Get_unwrapped(_Last), _STD _Pass_fn(_Pred));
}

template <class _RanIt, class _Pr>
_CONSTEXPR20 void _Make_heap_unchecked(_RanIt _First, _RanIt _Last, _Pr _Pred) {
    // make [_First, _Last) into a heap
    using _Diff   = _Iter_diff_t<_RanIt>;
    _Diff _Bottom = _Last - _First;
    for (_Diff _Hole = _Bottom >> 1; _Hole > 0;) { // shift for codegen
        // reheap top half, bottom to top
        --_Hole;
        _Iter_value_t<_RanIt> _Val(_STD move(*(_First + _Hole)));
        _STD _Pop_heap_hole_by_index(_First, _Hole, _Bottom, _STD move(_Val), _Pred);
    }
}

因为序列的范围是 [_First, _Last) 所以这里的 _Hole = _Bottom >> 1 - 1 就是最下面的子树根节点的序号(相对于 _First 的偏移)，然后通过 *(_First + _Hole) 将这个值拿到，再调用 _Pop_heap_hole_by_index 进行子树的调整，然后通过 --_Hole 依次向上调整子树即可，然后看下 _Pop_heap_hole_by_index 内部。

template <class _RanIt, class _Ty, class _Pr>
_CONSTEXPR20 void _Pop_heap_hole_by_index(
    _RanIt _First, _Iter_diff_t<_RanIt> _Hole, _Iter_diff_t<_RanIt> _Bottom, _Ty&& _Val, _Pr _Pred) {
    // percolate _Hole to _Bottom, then push _Val
    _STL_INTERNAL_CHECK(_Bottom > 0);

    using _Diff      = _Iter_diff_t<_RanIt>;
    const _Diff _Top = _Hole;
    _Diff _Idx       = _Hole;

    // Check whether _Idx can have a child before calculating that child's index, since
    // calculating the child's index can trigger integer overflows
    const _Diff _Max_sequence_non_leaf = (_Bottom - 1) >> 1; // shift for codegen
    while (_Idx < _Max_sequence_non_leaf) { // move _Hole down to larger child
        _Idx = 2 * _Idx + 2;
        if (_DEBUG_LT_PRED(_Pred, *(_First + _Idx), *(_First + (_Idx - 1)))) {
            --_Idx;
        }
        *(_First + _Hole) = _STD move(*(_First + _Idx));
        _Hole             = _Idx;
    }

    if (_Idx == _Max_sequence_non_leaf && _Bottom % 2 == 0) { // only child at bottom, move _Hole down to it
        *(_First + _Hole) = _STD move(*(_First + (_Bottom - 1)));
        _Hole             = _Bottom - 1;
    }

    _STD _Push_heap_by_index(_First, _Hole, _Top, _STD forward<_Ty>(_Val), _Pred);
}

template <class _RanIt, class _Ty, class _Pr>
_CONSTEXPR20 void _Push_heap_by_index(
    _RanIt _First, _Iter_diff_t<_RanIt> _Hole, _Iter_diff_t<_RanIt> _Top, _Ty&& _Val, _Pr _Pred) {
    // percolate _Hole to _Top or where _Val belongs
    using _Diff = _Iter_diff_t<_RanIt>;
    for (_Diff _Idx                                                          = (_Hole - 1) >> 1; // shift for codegen
         _Top < _Hole && _DEBUG_LT_PRED(_Pred, *(_First + _Idx), _Val); _Idx = (_Hole - 1) >> 1) { // shift for codegen
        // move _Hole up to parent
        *(_First + _Hole) = _STD move(*(_First + _Idx));
        _Hole             = _Idx;
    }

    *(_First + _Hole) = _STD forward<_Ty>(_Val); // drop _Val into final hole
}

这里的函数就是用来调整子树，和第一章讲解的调整方式有点不一样，这里是先把子树的根节点与最大的孩子节点交换，然后一直交换的叶子节点，然后从叶子节点开始向上调整，即如果比父节点大就交换，否则停止。_Pop_heap_hole_by_index 的前面部分就是交换到叶子节点，_Push_heap_by_index 就是向上调整的过程。

插入元素

插入元素使用 push，就是先调用容器的 push_back 方法把元素插入到末尾，然后 push_heap 调整堆

    void push(const value_type& _Val) {
        c.push_back(_Val);
        _STD push_heap(c.begin(), c.end(), _STD _Pass_fn(comp));
    }

    void push(value_type&& _Val) {
        c.push_back(_STD move(_Val));
        _STD push_heap(c.begin(), c.end(), _STD _Pass_fn(comp));
    }

	_EXPORT_STD template <class _RanIt, class _Pr>
_CONSTEXPR20 void push_heap(_RanIt _First, _RanIt _Last, _Pr _Pred) {
    // push *(_Last - 1) onto heap at [_First, _Last - 1)
    _STD _Adl_verify_range(_First, _Last);
    const auto _UFirst = _STD _Get_unwrapped(_First);
    auto _ULast        = _STD _Get_unwrapped(_Last);
    using _Diff        = _Iter_diff_t<_RanIt>;
    _Diff _Count       = _ULast - _UFirst;
    if (2 <= _Count) {
        _Iter_value_t<_RanIt> _Val(_STD move(*--_ULast));
        _STD _Push_heap_by_index(_UFirst, --_Count, _Diff(0), _STD move(_Val), _STD _Pass_fn(_Pred));
    }
}

push_heap 里就是调用上面提到的 _Push_heap_by_index 从叶子节点向上调整，这里 2 <= _Count 就是如果只有 1 个元素肯定就不用调整了。

删除元素

删除元素就是先调用 pop_heap，然后调用容器的 pop_back 删除末尾的元素。

    void pop() {
        _STD pop_heap(c.begin(), c.end(), _STD _Pass_fn(comp));
        c.pop_back();
    }

_Pop_heap_unchecked 中里的 2 <= _Last - _First 判断也是当堆里只有一个元素的时候，就不需要调整了，直接容器 pop_back 掉就可以了。
_Pop_heap_hole_unchecked 里的 *_Dest = _STD move(*_First) 就是把根节点放到末尾节点，_Val 里保存了之前的末尾元素，然后 _Pop_heap_hole_by_index 和堆初始化里用的一样，把更大的孩子节点依次上移，然后再把之前的末尾元素的值向上调整。

_EXPORT_STD template <class _RanIt, class _Pr>
_CONSTEXPR20 void pop_heap(_RanIt _First, _RanIt _Last, _Pr _Pred) {
    // pop *_First to *(_Last - 1) and reheap
    _STD _Adl_verify_range(_First, _Last);
    _STD _Pop_heap_unchecked(_STD _Get_unwrapped(_First), _STD _Get_unwrapped(_Last), _STD _Pass_fn(_Pred));
}

template <class _RanIt, class _Pr>
_CONSTEXPR20 void _Pop_heap_unchecked(_RanIt _First, _RanIt _Last, _Pr _Pred) {
    // pop *_First to *(_Last - 1) and reheap
    if (2 <= _Last - _First) {
        --_Last;
        _Iter_value_t<_RanIt> _Val(_STD move(*_Last));
        _STD _Pop_heap_hole_unchecked(_First, _Last, _Last, _STD move(_Val), _Pred);
    }
}
template <class _RanIt, class _Ty, class _Pr>
_CONSTEXPR20 void _Pop_heap_hole_unchecked(_RanIt _First, _RanIt _Last, _RanIt _Dest, _Ty&& _Val, _Pr _Pred) {
    // pop *_First to *_Dest and reheap
    // precondition: _First != _Last
    // precondition: _First != _Dest
    *_Dest      = _STD move(*_First);
    using _Diff = _Iter_diff_t<_RanIt>;
    _STD _Pop_heap_hole_by_index(
        _First, static_cast<_Diff>(0), static_cast<_Diff>(_Last - _First), _STD forward<_Ty>(_Val), _Pred);
}

http://www.niftyadmin.cn/n/5695047.html

相关文章

c语言：二叉树的创建、前序遍历、中序遍历、后续遍历

c语言：二叉树的创建、前序遍历、中序遍历、后续遍历

代码中创建的二叉树如下图 013##4##25##6##代码&#xff1a; #include <stdio.h> #include <stdlib.h>typedef struct Tree{int value;struct Tree* lchild;struct Tree* rchild; } Tree;// 创建节点 Tree* Tree_createnode(int value){Tree* node (Tree* )mallo…
阅读更多...
别再熬夜赶稿！AI自动成文插图，惊呆我了，效果如何？

别再熬夜赶稿！AI自动成文插图，惊呆我了，效果如何？

今天试了下 Napkin 这个工具&#xff0c;发现简直是做自媒体专业文的写作神器&#xff0c;可以把已经准备好的文章快速配上数据图。 当然也可以一句简单的 prompt 生成文章&#xff0c;然后针对每一段可以生成对应的插图&#xff0c;还在在此基础上进一步调整&#xff0c;太牛了…
阅读更多...
【Java 并发编程】多线程安全问题（上）

【Java 并发编程】多线程安全问题（上）

前言 虽然并发编程让我们的 CPU 核心能够得到充分的使用&#xff0c;程序运行效率更高效。但是也会引发一些问题。比如当进程中有多个并发线程进入一个重要数据的代码块时&#xff0c;在修改数据的过程中&#xff0c;很有可能引发线程安全问题&#xff0c;从而造成数据异常。 p…
阅读更多...
『网络游戏』窗口基类【06】

『网络游戏』窗口基类【06】

创建脚本&#xff1a;WindowRoot.cs 编写脚本&#xff1a; 修改脚本&#xff1a;LoginWnd.cs 修改脚本&#xff1a;LoadingWnd.cs 修改脚本&#xff1a;ResSvc.cs 修改脚本&#xff1a;LoginSys.cs 运行项目 - 功能不变 本章结束
阅读更多...
二维数组的旋转与翻转（C++）（上（这只是简单讲解））

二维数组的旋转与翻转（C++）（上（这只是简单讲解））

二维数组的旋转与翻转&#xff08;C&#xff09; 引言 在计算机科学中&#xff0c;二维数组是一种常见的数据结构&#xff0c;广泛应用于图像处理、数据挖掘、机器学习等多个领域。二维数组的旋转与翻转是处理二维数据时经常需要用到的操作。本文将详细介绍二维数组的旋转与翻…
阅读更多...
101 公司战略的基本概念

101 公司战略的基本概念

公司战略的概念 传统概念&#xff08;战略是终点途径&#xff09;&#xff1a;计划性、全局性、长期性现代概念&#xff08;战略是途径&#xff09;&#xff1a;应变性、竞争性、风险性综合概念&#xff08;前二者的折中&#xff09;&#xff1a;预先性、反应性公司的使命与目标…
阅读更多...
Go语言实现长连接并发框架 - 请求分发器

Go语言实现长连接并发框架 - 请求分发器

文章目录 前言接口结构体接口实现项目地址最后 前言 你好&#xff0c;我是醉墨居士&#xff0c;我们上篇博客实现了任务管理器的功能&#xff0c;接下来这篇博客我们将要实现请求分发模块的开发 接口 trait/dispatcher.go type Dispatcher interface {Start()Dispatch(conn…
阅读更多...
安装DNS

安装DNS

在 CentOS 7 上安装并配置 BIND 以实现 DNS 的正向和反向解析可以按照以下步骤进行&#xff1a; 安装 BIND 打开终端并运行以下命令来安装 BIND 及其工具&#xff1a; yum install bind bind-utils -y配置 BIND 编辑主配置文件&#xff1a; 使用文本编辑器打开 BIND 的主配…
阅读更多...
最新文章

Copyright @ 2022~2023