【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底层实现的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1096357

相关文章

Python实现终端清屏的几种方式详解

《Python实现终端清屏的几种方式详解》在使用Python进行终端交互式编程时,我们经常需要清空当前终端屏幕的内容,本文为大家整理了几种常见的实现方法,有需要的小伙伴可以参考下... 目录方法一:使用 `os` 模块调用系统命令方法二:使用 `subprocess` 模块执行命令方法三:打印多个换行符模拟

SpringBoot+EasyPOI轻松实现Excel和Word导出PDF

《SpringBoot+EasyPOI轻松实现Excel和Word导出PDF》在企业级开发中,将Excel和Word文档导出为PDF是常见需求,本文将结合​​EasyPOI和​​Aspose系列工具实... 目录一、环境准备与依赖配置1.1 方案选型1.2 依赖配置(商业库方案)二、Excel 导出 PDF

Python实现MQTT通信的示例代码

《Python实现MQTT通信的示例代码》本文主要介绍了Python实现MQTT通信的示例代码,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一... 目录1. 安装paho-mqtt库‌2. 搭建MQTT代理服务器(Broker)‌‌3. pytho

Spring的RedisTemplate的json反序列泛型丢失问题解决

《Spring的RedisTemplate的json反序列泛型丢失问题解决》本文主要介绍了SpringRedisTemplate中使用JSON序列化时泛型信息丢失的问题及其提出三种解决方案,可以根据性... 目录背景解决方案方案一方案二方案三总结背景在使用RedisTemplate操作redis时我们针对

使用zip4j实现Java中的ZIP文件加密压缩的操作方法

《使用zip4j实现Java中的ZIP文件加密压缩的操作方法》本文介绍如何通过Maven集成zip4j1.3.2库创建带密码保护的ZIP文件,涵盖依赖配置、代码示例及加密原理,确保数据安全性,感兴趣的... 目录1. zip4j库介绍和版本1.1 zip4j库概述1.2 zip4j的版本演变1.3 zip4

python生成随机唯一id的几种实现方法

《python生成随机唯一id的几种实现方法》在Python中生成随机唯一ID有多种方法,根据不同的需求场景可以选择最适合的方案,文中通过示例代码介绍的非常详细,需要的朋友们下面随着小编来一起学习学习... 目录方法 1:使用 UUID 模块(推荐)方法 2:使用 Secrets 模块(安全敏感场景)方法

Spring StateMachine实现状态机使用示例详解

《SpringStateMachine实现状态机使用示例详解》本文介绍SpringStateMachine实现状态机的步骤,包括依赖导入、枚举定义、状态转移规则配置、上下文管理及服务调用示例,重点解... 目录什么是状态机使用示例什么是状态机状态机是计算机科学中的​​核心建模工具​​,用于描述对象在其生命

Spring Boot 结合 WxJava 实现文章上传微信公众号草稿箱与群发

《SpringBoot结合WxJava实现文章上传微信公众号草稿箱与群发》本文将详细介绍如何使用SpringBoot框架结合WxJava开发工具包,实现文章上传到微信公众号草稿箱以及群发功能,... 目录一、项目环境准备1.1 开发环境1.2 微信公众号准备二、Spring Boot 项目搭建2.1 创建

IntelliJ IDEA2025创建SpringBoot项目的实现步骤

《IntelliJIDEA2025创建SpringBoot项目的实现步骤》本文主要介绍了IntelliJIDEA2025创建SpringBoot项目的实现步骤,文中通过示例代码介绍的非常详细,对大家... 目录一、创建 Spring Boot 项目1. 新建项目2. 基础配置3. 选择依赖4. 生成项目5.

SpringBoot结合Docker进行容器化处理指南

《SpringBoot结合Docker进行容器化处理指南》在当今快速发展的软件工程领域,SpringBoot和Docker已经成为现代Java开发者的必备工具,本文将深入讲解如何将一个SpringBo... 目录前言一、为什么选择 Spring Bootjavascript + docker1. 快速部署与