数据结构—堆(完全解析)

news/2024/3/29 20:34:42/文章来源:https://blog.csdn.net/Solititude/article/details/129182217

数据结构—堆(完全解析)

数据结构——堆(Heap)大根堆、小根堆

详解数据结构——堆

堆的基本存储

【从堆的定义到优先队列、堆排序】 10分钟看懂必考的数据结构——堆

【堆/排序】堆排序的两种建堆方法

【算法】排序算法之堆排序

C++:浅析STL之priority_queue构建大根堆与小根堆

基本概念

堆通常是一个可以被看做一棵完全二叉树的数组对象

堆满足下列性质:

  • 堆中某个节点的值总是不大于或不小于其父节点的值
  • 堆总是一棵完全二叉树

Min-heap(大根堆): 父节点的值小于或等于子节点的值

Max-heap(小根堆): 父节点的值大于或等于子节点的值
在这里插入图片描述

堆的存储

一般都用数组来表示堆,i结点的父结点下标就为(i–1)/2

它的左右子结点下标分别为2 * i + 1和2 * i + 2

如第0个结点左右子结点下标分别为1和2

在这里插入图片描述

堆的插入和上浮

  • 当一个新元素想要插入这个堆的时候,我们首先把他放到这个堆的末尾
  • 然后依据堆的特性,对它的位置进行调整,由于要保持父结点的值要永远少于其子节点的值,而2的直接父节点6大于了它,所以要把他们两的位置对换
  • 对换完毕后,再检查这个堆的状态,发现其父节点3仍然大于自己,所以继续往上和3对换
  • 结束后和0比较,0不大于自己,所以停留在原地不动,插入结束
  • 简单来说,插入一个结点就是将该元素插入到堆的尾部,然后不断上浮调整位置,直至满足堆的条件

在这里插入图片描述

堆的删除和下沉

  • 删除一般指的都是删除堆顶元素,在堆顶元素被拿掉后,将末尾元素置换上来,进行下沉操作
  • 由于这是最小堆,堆顶一定是最小元素,首先6大于左结点1,需要下沉,
  • 下沉完以后继续和它子节点比较,发现左结点2小于自身,继续下沉
  • 最后89都比6大,停止下沉。
  • 总结来说,意思就是删除堆顶元素后,用末尾元素补上,然后不断下沉,直至满足堆的条件

在这里插入图片描述

堆的建立

自顶向下,时间复杂度为O(nlogn)

在这里插入图片描述
自下而上,时间复杂度为O(n)

从倒数第二排开始,对每一个父节点进行下滤操作,直到根节点操作完毕

在这里插入图片描述
在这里插入图片描述

堆的应用

优先队列

优先队列有两个操作,插入队列和弹出最小元素

在这里插入图片描述

优先队列利用小根堆实现,弹出根节点即可实现弹出最小元素的操作

在这里插入图片描述

弹出后要将剩余的元素调整为堆,将最后一个元素放到根节点,进行下沉操作即可

在这里插入图片描述
在这里插入图片描述

堆排序

  • 先把数组构造成一个大顶堆(父亲节点大于其子节点),然后把堆顶(数组最大值,数组第一个元素)和数组最后一个元素交换,这样就把最大值放到了数组最后边
  • 把数组度-1,再进行构造堆把剩余的第二大值放到堆顶,输出堆顶(放到剩余未排序数组最后面),依次类推,直至数组排序完成
#include <iostream>
#include <algorithm>
using namespace std;
void max_heapify(int arr[], int start, int end) {//建立父节点指标和子节点指标int dad = start;int son = dad * 2 + 1;while (son <= end) { //若子节点指标在范围内才做比较if (son + 1 <= end && arr[son] < arr[son + 1]) //先比较两个子节点大小,选择最大的son++;if (arr[dad] > arr[son]) //如果父节点大于子节点代表调整完毕,直接跳出函数return;else { //否则交换父子内容再继续子节点和孙节点比较swap(arr[dad], arr[son]);dad = son;son = dad * 2 + 1;}}
}
void heap_sort(int arr[], int len) {//初始化,i从最后一个父节点开始调整for (int i = len / 2 - 1; i >= 0; i--)max_heapify(arr, i, len - 1);//先将第一个元素和已经排好的元素前一位做交换,再从新调整(刚调整的元素之前的元素),直到排序完毕for (int i = len - 1; i > 0; i--) {swap(arr[0], arr[i]);max_heapify(arr, 0, i - 1);}
}
int main() {int arr[] = { 3, 5, 3, 0, 8, 6, 1, 5, 8, 6, 2, 4, 9, 4, 7, 0, 1, 8, 9, 7, 3, 1, 2, 5, 9, 7, 4, 0, 2, 6 };int len = (int) sizeof(arr) / sizeof(*arr);heap_sort(arr, len);for (int i = 0; i < len; i++)cout << arr[i] << ' ';cout << endl;return 0;
}

C++ STL大根堆小根堆

在C++中优先队列默认的是大根堆,如果用小根堆则加入greater

#include <queue>
priority_queue<int, vector<int>>s;//大根堆
priority_queue<int, vector<int>, less<int>>s;//less表示按照递减(从大到小)的顺序插入元素,大根堆
priority_queue<int, vector<int>, greater<int>>s;//greater表示按照递增(从小到大)的顺序插入元素,小根堆

支持的顺序容器:vector,queue,默认是vector

priority_queue类能按照有序的方式在底层数据结构中执行插入、删除操作

q.pop();//删除优先队列priority_queuel的最高优先级元素(通过调用底层容器的pop_back()实现)
q.push(item);//在priority._queue优先级顺序合适的位置添加创建一个值为item的元素(通过调用底层容器的push_back()操作实现)
q.emplace(args);//在priority_queue优先级顺序合适的位置添加个由args构造的元素(通过调用底层容器的emplace_back()操作实现)
q.top();//返回priority_queue的首元素的引用(通过调用底层容器的front()操作实现)
q.empty();//判断q是否为空,空返回true,否则返回false(通过调用底层容器的empty()操作实现)
q.size();//返回q中的元素个数(通过调用底层容器的size()操作实现)
swap(q,p);//交换两个优先队列priority_queue p,q的内容,p和q的底层容器类型也必须相同(通过调用底层容器的swap0操纵实现)

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.luyixian.cn/news_show_73064.aspx

如若内容造成侵权/违法违规/事实不符,请联系dt猫网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Mybatis学习记录

Mybatis学习记录一、MyBatis简介1.1、MyBatis历史1.2、MyBatis特性1.3、MyBatis下载1.4、和其他持久化层技术对比二、MyBatis框架搭建2.1、加入依赖2.2、创建MyBatis的核心配置文件2.3、创建Mapper接口2.4、 创建MyBatis的映射文件2.5、 测试环境2.6、 加入Log4j日志功能三、核…

Array.apply(null,{length: 99}) 逻辑解析

一、基础概述 vue 教程中有一段 demo code&#xff0c;如下&#xff1a; render: function (createElement) {return createElement(div,Array.apply(null, { length: 20 }).map(function () {return createElement(p, hi)})) }这个表达式Array.apply(null, { length: 20 })有…

Leetcode第450题删除二叉搜索树中的结点|C语言

题目&#xff1a; 给定一个二叉搜索树的根节点 root 和一个值 key&#xff0c;删除二叉搜索树中的 key 对应的节点&#xff0c;并保证二叉搜索树的性质不变。返回二叉搜索树&#xff08;有可能被更新&#xff09;的根节点的引用。 一般来说&#xff0c;删除节点可分为两个步骤…

【python】用plotly绘制正二十面体

文章目录顶点棱实现正二十面体plotly 的 Python 软件包是一个开源的代码库&#xff0c;它基于 plot.js&#xff0c;而后者基于 d3.js。我们实际使用的则是一个对 plotly 进行封装的库&#xff0c;名叫 cufflinks&#xff0c;能让你更方便地使用 plotly 和 Pandas 数据表协同工作…

最新文件快递柜系统网站源码-Fastapi+Sqlite3+Vue2+ElementUI-简洁好用

## 主要特色 - [x] 轻量简洁:Fastapi+Sqlite3+Vue2+ElementUI - [x] 轻松上传:复制粘贴,拖拽选择 - [x] 多种类型:文本,文件 - [x] 防止爆破:错误次数限制 - [x] 防止滥用:IP限制上传次数 - [x] 口令分享:随机口令,存取文件,自定义次数以及有效期 - [x] 匿名分享:无…

BurpSuite实战教程02-BurpSuite+夜神模拟器抓包教程

工具介绍 BurpSuite BurpSuite是用于“攻击”web 应用程序的集成平台&#xff08;java编写&#xff09;&#xff0c;包含了许多工具。Burp Suite为这些工具设计了许多接口&#xff0c;以加快攻击应用程序的过程。所有工具都共享一个请求&#xff0c;并能处理对应的HTTP 消息、…

使用Autoware标定工具包联合标定相机和激光雷达

前面文章介绍了&#xff0c;安装autoware标定工具包、ros驱动usb相机、robosense-16线激光雷达的使用&#xff0c;本文记录使用Autoware标定工具包联合标定相机和激光雷达的过程。1.ros驱动相机&#xff0c;启动相机&#xff1b;启动激光雷达2.联合录制bag包rosbag record -a 参…

k8s1.23.0+ubuntu20.04+docker23+hyperv

问题 k8s node节点加入到集群时卡住 “[preflight] Running pre-flight checks” # master节点重新生成加入命令 kubeadm token create --ttl 0 --print-join-command参考 注意 k8s1.24使用containerd而不再使用docker&#xff0c;因此使用k8s1.23版本 环境 k8s: 1.23.0 u…

TestNG和Junit的区别,测试框架该如何选择?

要想知道两个框架的区别&#xff0c;首先分别介绍一下两个框架。 TestNG是一个java中的开源自动化测试框架&#xff0c;其灵感来自JUnit和NUnit&#xff0c;TestNG还涵盖了JUnit4整个核心的功能&#xff0c;但引入了一些新的功能&#xff0c;使其功能更强大&#xff0c;使用更…

记一次docker虚拟机横向移动渗透测试

本次渗透在几个docker虚拟机间多次横向移动&#xff0c;最终找到了一个可以进行docker逃逸的出口&#xff0c;拿下服务器。渗透过程曲折但充满了乐趣&#xff0c;入口是172.17.0.6的docker虚拟机&#xff0c;然后一路横向移动&#xff0c;最终在172.17.0.2出实现了docker逃逸&a…

【vue2每日小知识】实现store中modules模块的封装与自动导入

&#x1f973;博 主&#xff1a;初映CY的前说(前端领域) &#x1f31e;个人信条&#xff1a;想要变成得到&#xff0c;中间还有做到&#xff01; &#x1f918;本文核心&#xff1a;省去我们store仓库中分模块时的需要每次导入index的问题 目录 【前言】在store中如何简…

ELK日志分析--Filebeat

ELK架构 Filebeat简介 Filebeat安装 Filebeat简单使用 专用日志搜集模块 案例模块-Nginx 模块 重读日志文件 使用Processors(处理器)过滤和增强数据 1.ELK架构 2.Filebeat简介 可以使用 Filebeat 收集各种日志&#xff0c;之后发送到指定的目标系统上&#xff0c;但是同…

软件测试面试题 —— 整理与解析(1)

&#x1f60f;作者简介&#xff1a;博主是一位测试管理者&#xff0c;同时也是一名对外企业兼职讲师。 &#x1f4e1;主页地址&#xff1a;&#x1f30e;【Austin_zhai】&#x1f30f; &#x1f646;目的与景愿&#xff1a;旨在于能帮助更多的测试行业人员提升软硬技能&#xf…

【华为OD机试真题】用 C++ 实现 - 数字加减游戏

最近更新的博客 华为OD机试 - 入栈出栈(C++) | 附带编码思路 【2023】 华为OD机试 - 箱子之形摆放(C++) | 附带编码思路 【2023】 华为OD机试 - 简易内存池 2(C++) | 附带编码思路 【2023】 华为OD机试 - 第 N 个排列(C++) | 附带编码思路 【2023】 华为OD机试 - 考古…

程序员如何发展第二职业?这几种副业方式超赚钱

很多程序员曾表示&#xff0c;虽然月薪一两万&#xff0c;但有时候还是会焦虑。 尤其是遇上了年初裁员年底裁员这样的就业环境&#xff0c;焦虑就会逐步放大&#xff0c;这时候副业赚钱的重要性就体现出来了。 发展第二职业&#xff0c;可以让程序员们增加抗风险能力&#xf…

数据结构-考研难点代码突破(树型查找 - 红黑树(RBT)插入流程图,删除)

文章目录1. 红黑树的定义和性质红黑树的插入操作流程红黑树的删除&#xff08;了解&#xff09;1. 红黑树的定义和性质 红黑树查找与删除的效率和AVL树相同。 但是因为AVL树在插入或删除节点可能破坏AVL树结构&#xff0c;而重新调整树的开销大。所以引出了红黑树。 红黑树的…

【Jmeter】ForEach控制器

一、什么是ForEach控制器 ForEach控制器是遍历某个数组读取不同的变量值&#xff0c;来控制其下的采样器或控制器执行一次或多次。而这个数组可以是用户自定义变量&#xff0c;也可以是从前面接口请求中提取到需要的数据&#xff0c;然后进行遍历循环。 二、ForEach控制器相关…

技能提升:Python技术应用工程师职业技能提升

职业技术培训-Python技术应用工程师分为高级培训班、中级培训班及初级培训班。 Python是一种跨平台的计算机程序设计语言&#xff0c;是一个高层次的结合了解释性、编译性、互动性和面向对象的语言。最初被设计用于编写自动化脚本Shell&#xff08;适用于Linux操作系统&#xf…

Linux PWM 开发指南

Linux PWM 开发指南 1 概述 1.1 编写目的 介绍 PWM 模块的详细设计方便相关人员进行 PWM 模块的代码设计开发。 1.2 使用范围 适用于 Linux-3.10&#xff0c;linux-4.4 和 Linux-4.9 内核&#xff0c;Linux-5.4 内核。 1.3 相关人员 PWM 驱动的开发人员/维护人员等 2 术…

数据库系统概论——绪论

1、绪论 1.1、数据库系统概述 数据库系统的构成示意图 1.1.1、数据库系统基本概念 基本概念&#xff1a;数据、数据库、数据库管理系统和数据库系统 1&#xff09;数据&#xff08;data&#xff09; 定义&#xff1a;描述事物的符号记录称为数据数据是数据库中存储的基本对象…