STL —heap算法源码刨析 make_heap、push_heap、pop_heap、sort_heap操作分析

news/2024/9/19 11:17:04/ 标签: c++, 算法, heap, STL, 大堆、小堆

STL —heap算法源码刨析

  • heap算法概述
    • push_heap 插入元素
    • pop_heap 取出根节点元素
    • sort_heap 按极值存放元素
    • make_heap 将一段现有数据构造成heap
    • 程序测试

heap_2">heap算法概述

heap的内部是一个完全二叉树，将极值存放在根节点。这个里的极值可分为最大值、最小值。根据极值意义的不同可分为大堆和小堆。为了方便解释，以下的讲解内容都以大堆（max-heap）的例子讲解。
大顶堆：
根节点（堆顶元素）是所有节点中的最大值（父节点都大于左右子节点）。
小顶堆：
小顶堆中的根节点是所有节点中的最小值（父节点都小于左右子节点）。

如上图所示，A即为这个列表中的极值。在查找极值时极为方便。同时因为是一个完全二叉树，所以除了叶子节点外，其他的节点都存在。因此可以通过索引值，来找到父节点和左右子节点之间的关系。当父节点索引值为i时，左子节点索引值2i+1,右子节点索引值为2i+2。
具体原理可查看此博客：堆排序中 i 位置的节点的子节点位置为 2i+1, 2i+2, 父节点为 (i-1) / 2

heap__12">push_heap 插入元素


数据插入示意图

将要插入的元素，放入容器的尾端。通过调用push_heap()函数，将尾端的元素放入到完全二叉树的合适位置。

//计算元素之间的距离
template<class ForwardIterator>
typename std::iterator_traits<ForwardIterator>::difference_type Distance(ForwardIterator first, ForwardIterator last)
{typename std::iterator_traits<ForwardIterator>::difference_type n = 0;while (first != last){++first;++n;}return n;
}//获取元素类型
template<class Iterator>
inline typename std::iterator_traits<Iterator>::value_type* value_Type(const Iterator&)
{return static_cast<std::iterator_traits<Iterator>::value_type *> (0);
}//获取表示距离的类型
template<class Iterator>
inline typename std::iterator_traits<Iterator>::difference_type* distance_type(const Iterator&)
{return static_cast<std::iterator_traits<Iterator>::difference_type *> (0);
}
template<class RandomAcessIterator, class Distance, class T>
void _push_heap(RandomAcessIterator first, Distance holeIndex, Distance topIndex, T value)
{Distance parent = (holeIndex - 1) / 2; //找到父节点while (holeIndex > topIndex && *(first + parent) < value) //当索引值不为根节点时，或者父节点小于插入空节点时{*(first + holeIndex) = *(first + parent);//父节点的值复制给空节点holeIndex = parent; //父节点索引值复制给空节点parent = (holeIndex-1) / 2; //查找此时空节点的父节点}*(first + holeIndex) = value; //将值复制到此时的空节点上
}template<class RandomAcessIterator, class Distance, class T>
inline void _push_heap_aux(RandomAcessIterator first, RandomAcessIterator last, Distance*, T*)
{int count = last - first;_push_heap(first, Distance((last - first) - 1), Distance(0), T(*(last - 1)));
}template <class RandomAcessIterator>
inline void USD_push_heap(RandomAcessIterator first, RandomAcessIterator last)
{_push_heap_aux(first, last, distance_type(first), value_Type(first));
}

这是是一个插入操作，将数据写入到字符串的尾端。找到尾端所对应的父节点，进行对比。如果大于父节点，两个节点对调。找到根节点或者插入空节点小于父节点时，循环操作结束。此时插入的值被放入合适的位置。元素的插入，可参考示意图的操作。

heap__73">pop_heap 取出根节点元素

调用 函数pop_heap(),会将根节点的值取出来，存在放在容器的尾端。同时会按照完全二叉树的规则重新移动剩余的元素，找出剩余元素中的极值，存放在根节点中，构建出一个新的完全二叉树。此时要取出的元素位于尾部，再通过容器自身的操作，取出尾部的元素。
元素取出示意图
元素取出示意图

template<class RandomAcessIterator, class Distance, class T>
void _adjust_heap(RandomAcessIterator first, Distance holeIndex, Distance len, T value)
{Distance topIndex = holeIndex; //根节点Distance sencondChild = 2 * holeIndex + 2; //右子节点while (sencondChild < len){if (*(first + sencondChild) < *(first + sencondChild - 1)) //右子节点与左子节点进行比较{sencondChild--; //通过移动，找到左子节点}*(first + holeIndex) = *(first + sencondChild);//将较大的值复制给空值元素所在的位置holeIndex = sencondChild; //空值元素移动到较大值元素位置上sencondChild = 2 * sencondChild + 2; //再次查找对应的右子节点}if (sencondChild == len) //此时右子节点等于树的长度，那么右子树不存在，将左子树元素复制给空值元素{*(first + holeIndex) = *(first + sencondChild-1);holeIndex = sencondChild-1;}_push_heap(first, holeIndex, topIndex,value);//将原二叉树的尾部元素，插入到现在空值元素位置上
}template<class RandomAcessIterator,class T,class Distance>
inline void _pop_heap(RandomAcessIterator first, RandomAcessIterator last, RandomAcessIterator result,T value,Distance *)
{*result = *first;_adjust_heap(first, Distance(0), Distance(last - first), value);
}template<class RandomAcessIterator,class T>
inline void _pop_heap_aux(RandomAcessIterator first, RandomAcessIterator last,T*)
{_pop_heap(first, last-1, last - 1, T(*(last - 1)), distance_type(first));
}template<class RandomAcessIterator>
inline void USD_pop_heap(RandomAcessIterator first, RandomAcessIterator last)
{_pop_heap_aux(first,last,value_Type(first));
}

此算法中的核心逻辑调用_adjust_heap()，首先holeIndex = 0，此时空值元素代表的是根节点，找到根节点对应的右子节点，根节点的右子节点和左子节点进行相比。空值元素与相比后较大值元素进行对换，此时较大值元素就作为了根节点，同时空值元素，移动到了较大值的位置。重复上述操作在继续查找控制元素的右子节点，与它的左子节点进行对比。只到所查值的右子节点索引值大于树的长长度。则停止查找。查找结束后，将原完全二叉树的尾节点，复制到空值所在的位置。操作流程，可参考此函数的示意图。

heap__124">sort_heap 按极值存放元素

将元素按照极值，从尾到前开始存放元素
在这里插入图片描述在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

template<class RandomAcessIterator>
void USD_sort_heap(RandomAcessIterator first, RandomAcessIterator last)
{while (last - first>1){USD_pop_heap(first,last--);}
}

通过使用pop_heap()操作，将结果存放在尾部，同时缩短last的索引值。这样每pop_heap一次，就会构造一个新的二叉树，同时尾部会存放上一个二叉树的根节点。

heap_heap_142">make_heap 将一段现有数据构造成heap

容器中存放一段数据，通过make操作后，会更改容器中元素的位置。从而满足 堆的要求。

template<class RandomAcessIterator,class T,class Distance>
void _make_heap(RandomAcessIterator first, RandomAcessIterator last, T*, Distance*)
{if (last - first<2){return;}Distance len = last - first;Distance parent = (len - 2) / 2; //最后一个父节点while (true){_adjust_heap(first, parent, len, *(first+ parent));if (parent == 0){return;}parent--;}
}template<class RandomAcessIterator>
inline void USD_make_heap(RandomAcessIterator first, RandomAcessIterator last)
{_make_heap( first,last, value_Type(first), distance_type(first));
}

此算法的思路，首先找到最后一个父节点。通过调用_adjust_heap()函数，来调整此时的父节点和左右两个子节点之间的关系。来满足heap的条件。当此节点和其子节点调整结束后，通过移动parent索引值，找到下一个父节点再重复上一个操作。当查找到根节点即索引值为0时，heap构建完成。

程序测试

//heap.h
#pragma once
#include <algorithm>template<class ForwardIterator>
typename std::iterator_traits<ForwardIterator>::difference_type Distance(ForwardIterator first, ForwardIterator last)
{typename std::iterator_traits<ForwardIterator>::difference_type n = 0;while (first != last){++first;++n;}return n;
}template<class Iterator>
inline typename std::iterator_traits<Iterator>::value_type* value_Type(const Iterator&)
{return static_cast<std::iterator_traits<Iterator>::value_type *> (0);
}template<class Iterator>
inline typename std::iterator_traits<Iterator>::difference_type* distance_type(const Iterator&)
{return static_cast<std::iterator_traits<Iterator>::difference_type *> (0);
}template<class RandomAcessIterator, class Distance, class T>
void _push_heap(RandomAcessIterator first, Distance holeIndex, Distance topIndex, T value)
{Distance parent = (holeIndex - 1) / 2;while (holeIndex > topIndex && *(first + parent) < value){*(first + holeIndex) = *(first + parent);holeIndex = parent;parent = (holeIndex-1) / 2;}*(first + holeIndex) = value;
}template<class RandomAcessIterator, class Distance, class T>
inline void _push_heap_aux(RandomAcessIterator first, RandomAcessIterator last, Distance*, T*)
{int count = last - first;_push_heap(first, Distance((last - first) - 1), Distance(0), T(*(last - 1)));
}template <class RandomAcessIterator>
inline void USD_push_heap(RandomAcessIterator first, RandomAcessIterator last)
{_push_heap_aux(first, last, distance_type(first), value_Type(first));
}template<class RandomAcessIterator, class Distance, class T>
void _adjust_heap(RandomAcessIterator first, Distance holeIndex, Distance len, T value)
{Distance topIndex = holeIndex;Distance sencondChild = 2 * holeIndex + 2;while (sencondChild < len){if (*(first + sencondChild) < *(first + sencondChild - 1)){sencondChild--;}*(first + holeIndex) = *(first + sencondChild);holeIndex = sencondChild;sencondChild = 2 * sencondChild + 2;}if (sencondChild == len){*(first + holeIndex) = *(first + sencondChild-1);holeIndex = sencondChild-1;}_push_heap(first, holeIndex, topIndex,value);
}template<class RandomAcessIterator,class T,class Distance>
inline void _pop_heap(RandomAcessIterator first, RandomAcessIterator last, RandomAcessIterator result,T value,Distance *)
{*result = *first;_adjust_heap(first, Distance(0), Distance(last - first), value);
}template<class RandomAcessIterator,class T>
inline void _pop_heap_aux(RandomAcessIterator first, RandomAcessIterator last,T*)
{_pop_heap(first, last-1, last - 1, T(*(last - 1)), distance_type(first));
}template<class RandomAcessIterator>
inline void USD_pop_heap(RandomAcessIterator first, RandomAcessIterator last)
{_pop_heap_aux(first,last,value_Type(first));
}template<class RandomAcessIterator>
void USD_sort_heap(RandomAcessIterator first, RandomAcessIterator last)
{while (last - first>1){USD_pop_heap(first,last--);}
}template<class RandomAcessIterator,class T,class Distance>
void _make_heap(RandomAcessIterator first, RandomAcessIterator last, T*, Distance*)
{if (last - first<2){return;}Distance len = last - first;Distance parent = (len - 2) / 2; //最后一个父节点while (true){_adjust_heap(first, parent, len, *(first+ parent));if (parent == 0){return;}parent--;}
}template<class RandomAcessIterator>
inline void USD_make_heap(RandomAcessIterator first, RandomAcessIterator last)
{_make_heap( first,last, value_Type(first), distance_type(first));
}

#include "heap.h"
#include <vector>int main()
{int a[5] = {1,2,3,4,5};std::vector<int> vecTest(a,a+5);USD_make_heap(vecTest.begin(), vecTest.end()); //5,4,3,1,2	vecTest.push_back(7);USD_push_heap(vecTest.begin(), vecTest.end()); //7,4,5,1,2,3USD_pop_heap(vecTest.begin(), vecTest.end());//5,4,3,1,2,7vecTest.pop_back();//5,4,3,1,2USD_sort_heap(vecTest.begin(), vecTest.end());//1,2,3,4,5return 0;
}

为了方便，上述实现都采用了“<”作为比较操作符。这块比较操作，可封装成仿函数，来满足用户自定义的比较操作。注意：写仿函数时，注意返回的bool值。从而决定构建的是max-heap或者min-heap。

如果想了解，算法封装仿函数操作可参考：STL算法详细解剖——单纯数据处理函数
此文章，列举了相同算法，封装仿函数与不封装仿函数两种形式。未了解过仿函数的读者，可做初步的了解。


http://www.ppmy.cn/news/1527215.html

相关文章

分类预测|2024年最新优化算法鹦鹉优化器PO|基于鹦鹉优化SVM支持向量机数据分类预测Matlab程序PO-SVM

分类预测|2024年最新优化算法鹦鹉优化器PO|基于鹦鹉优化SVM支持向量机数据分类预测Matlab程序PO-SVM

分类预测|2024年最新优化算法鹦鹉优化器PO|基于鹦鹉优化SVM支持向量机数据分类预测Matlab程序PO-SVM 文章目录 一、基本原理**原理****PO-SVM 流程****总结** 二、实验结果三、核心代码四、代码获取五、总结 一、基本原理 PO-SVM 是一种将鹦鹉优化算法&#xff08;Parrot Opti…
阅读更多...
【农信网-注册/登录安全分析报告】

【农信网-注册/登录安全分析报告】

前言 由于网站注册入口容易被黑客攻击&#xff0c;存在如下安全问题&#xff1a; 暴力破解密码&#xff0c;造成用户信息泄露短信盗刷的安全问题&#xff0c;影响业务及导致用户投诉带来经济损失&#xff0c;尤其是后付费客户&#xff0c;风险巨大&#xff0c;造成亏损无底洞…
阅读更多...
【SSRF漏洞】——gopherus工具伪造

【SSRF漏洞】——gopherus工具伪造

改变的确很难&#xff0c;但结果值得冒险 本文如有错误之处&#xff0c;还请各位师傅指正 目录 一.gopherus概述 二.gopherus安装使用 三.gopherus覆盖的服务 四.使用案例 web359&#xff1a; web360&#xff1a; 一.gopherus概述 Gopherus是一个专为生成Gopher协议Payloa…
阅读更多...
es操作的请求体

es操作的请求体

创建索引的请求体 插入数据 查询索引 删除数据
阅读更多...
怎么能让电脑屏幕显示多个监控画面？电脑监控如何多画面显示？

怎么能让电脑屏幕显示多个监控画面？电脑监控如何多画面显示？

想象一下&#xff0c;你的电脑屏幕变成了一个“指挥中心”&#xff0c;上面同时显示多个监控画面&#xff0c;每个角落都有重要的信息。无论是监控员工的工作情况、实时查看服务器状态&#xff0c;还是观看监控视频&#xff0c;一切尽在掌握中。这不是科幻电影里的场景&#xf…
阅读更多...
Rust GUI框架 tauri V2 项目创建

Rust GUI框架 tauri V2 项目创建

文章目录 Tauri 2.0创建应用文档移动应用开发 Android 前置要求移动应用开发 iOS 前置要求参考资料 Tauri 2.0 Tauri 是一个构建适用于所有主流桌面和移动平台的轻快二进制文件的框架。开发者们可以集成任何用于创建用户界面的可以被编译成 HTML、JavaScript 和 CSS 的前端框架…
阅读更多...
JS面试真题 part5

JS面试真题 part5

JS面试真题 part5 21、说说对事件循环的理解22、JavaScript本地存储方式有哪些&#xff1f;区别及应用场景&#xff1f;23、大文件上传如何断点续传&#xff1f;24、ajax原理是什么&#xff1f;如何实现&#xff1f;25、什么是防抖和节流&#xff1f;有什么区别&#xff1f;如何…
阅读更多...
HarmonyOS 实现沉浸式效果

HarmonyOS 实现沉浸式效果

&#x1f468;&#x1f3fb;‍&#x1f4bb; 热爱摄影的程序员 &#x1f468;&#x1f3fb;‍&#x1f3a8; 喜欢编码的设计师 &#x1f9d5;&#x1f3fb; 擅长设计的剪辑师 &#x1f9d1;&#x1f3fb;‍&#x1f3eb; 一位高冷无情的全栈工程师 欢迎分享 / 收藏 / 赞 / 在看…
阅读更多...
牛客周赛 Round 60（A,B,C,D,E,F）

牛客周赛 Round 60（A,B,C,D,E,F）

比赛链接 官方题解 这场基本都是数学题&#xff0c;官方题解讲的还不错&#xff0c;F能听懂的话其实不难。E是一个球盒模型的组合问题&#xff0c;F是化简递推式&#xff0c;成环时的解决方法很不错。 A 困难数学题 思路&#xff1a; 一个数异或两次结果为 0 0 0&#xff…
阅读更多...
CleanMyMac 5 for Mac 最新中文破解版下载 系统优化垃圾清理工具

CleanMyMac 5 for Mac 最新中文破解版下载 系统优化垃圾清理工具

今天给大家带来的是CleanMyMac最新款CleanMyMac 5&#xff0c;它是一个全面的Mac清理和维护工具&#xff0c;通过提供多项强大的功能&#xff0c;帮助用户简化日常维护任务&#xff0c;提升系统性能&#xff0c;同时保护个人隐私和安全。无论是新手还是经验丰富的Mac用户&#…
阅读更多...
Axure设计之表格列冻结（动态面板+中继器）

Axure设计之表格列冻结（动态面板+中继器）

在Web端产品设计中&#xff0c;复杂的表格展示是常见需求&#xff0c;尤其当表格包含大量列时&#xff0c;如何在有限的屏幕空间内优雅地展示所有信息成为了一个挑战。用户通常需要滚动查看隐藏列&#xff0c;但关键信息列&#xff08;如ID、操作按钮等&#xff09;在滚动时保持…
阅读更多...
【数据分析】标准误差与标准差的区别

【数据分析】标准误差与标准差的区别

标准误差&#xff08;Standard Error, SE&#xff09;和标准差&#xff08;Standard Deviation, SD&#xff09;是两个在统计学中非常重要的概念&#xff0c;但它们的含义和用途有所不同。以下是它们之间的主要区别&#xff1a; 定义&#xff1a; 标准差&#xff1a;衡量单个数…
阅读更多...
网络设备登录——《路由与交换技术》实验报告

网络设备登录——《路由与交换技术》实验报告

目录 一、实验目的 二、实验设备和环境 三、实验记录 1.通过 Console 登录 步骤1:连接配置电缆。 步骤2:启动PC,运行超级终端。 步骤3:进入Console 配置界面 2.通过 Telnet 登录 步骤1:通过 Console 接口配置 Telnet 用户。 步骤2:配置 super 口令 步骤3:配置登录欢迎…
阅读更多...
golang学习笔记25——golang 实现 MD5加密、RSA加密 和 Base64编码

golang学习笔记25——golang 实现 MD5加密、RSA加密 和 Base64编码

推荐学习文档 golang应用级os框架&#xff0c;欢迎stargolang应用级os框架使用案例&#xff0c;欢迎star案例&#xff1a;基于golang开发的一款超有个性的旅游计划app经历golang实战大纲golang优秀开发常用开源库汇总想学习更多golang知识&#xff0c;这里有免费的golang学习笔…
阅读更多...
在Unity UI中实现UILineRenderer组件绘制线条

在Unity UI中实现UILineRenderer组件绘制线条

背景介绍 在Unity的UI系统中&#xff0c;绘制线条并不像在3D世界中那样直观(使用Unity自带的LineRender组件在UI中连线并不方便,它在三维中更合适)。没有内置的工具来处理这种需求。如果你希望在UI元素之间绘制连接线&#xff08;例如在UI上连接不同的图标或控件&#xff09;&a…
阅读更多...
用 Python 实现将长 Markdown 文档从二级标题开始拆分

用 Python 实现将长 Markdown 文档从二级标题开始拆分

以下是一个简单的Python脚本&#xff0c;它可以将Markdown文档按照二级标题&#xff08;##&#xff09;进行拆分&#xff0c;并保存到指定的输出路径。 import osdef split_markdown_by_headers(input_path, output_folder):# 确保输出文件夹存在if not os.path.exists(output…
阅读更多...
如何快准稳 实现MySQL大表历史数据迁移？

如何快准稳 实现MySQL大表历史数据迁移？

历史迁移解决方案以微服务架构为基础&#xff0c;使用多种设计模式&#xff0c;如&#xff1a;单例、桥接、工厂、模板、策略等。其中涉及的核心技术有多线程、过滤器等&#xff0c;致力于解决MySQL大表迁移的问题&#xff0c;提供多种迁移模式&#xff0c;如&#xff1a;库到库…
阅读更多...
明明没有程序占用端口，但是启动程序却提示端口无法使用，项目也启动失败

明明没有程序占用端口，但是启动程序却提示端口无法使用，项目也启动失败

明明没有程序占用端口&#xff0c;但是启动程序却提示端口无法使用&#xff0c;项目也启动失败 win10、端口占用、port、netstat、used背景 曾在springboot中遇到过&#xff0c;新建spring cloud时又遇到这个问题&#xff0c;如果不从根本上解决&#xff0c;就需要改端口&…
阅读更多...
uniapp点击跳转到对应位置

uniapp点击跳转到对应位置

其实就是标签选择器 获取到对应标签所在的高度&#xff0c;然后用uni.pageScrollTo跳转&#xff0c;这是在正常页面上的跳转&#xff0c;scroll-view中更方便 <template><view class"product-page"><scroll-view scroll-y"true" class&quo…
阅读更多...
c语言--力扣简单题目（回文链表）讲解

c语言--力扣简单题目（回文链表）讲解

题目如下&#xff1a; 给你一个单链表的头节点 head &#xff0c;请你判断该链表是否为 回文链表。 如果是&#xff0c;返回 true &#xff1b;否则&#xff0c;返回 false 。 示例 1&#xff1a; 输入&#xff1a;head [1,2,2,1] 输出&#xff1a;true 示例 2&#xff1…
阅读更多...
最新文章

Copyright @ 2022~2023

友情链接： 我的编程经验分享 一条长河网 尧图网站开发 尧图建网站