当前位置: 首页 > news >正文

数据结构之<堆>的介绍

1.简介


堆是一种特殊的数据结构,通常用于实现优先队列。堆是一个可以被看作近似完全二叉树的结构,并且具有一些特殊的性质,根据这些性质,堆被分为最大堆(或者大根堆,大顶堆)和最小堆两种。
在这里插入图片描述

2.基本性质


  1. 完全二叉树结构:堆必须是一棵完全二叉树,即除了最底层,其他层都是满的,而且最底层的节点都尽量靠左排列,最后一行元素之间不可以有间隔。
  2. 堆序性质: 堆分为最大堆和最小堆两种。在最大堆中,任意节点的值都大于或等于其子节点的值;在最小堆中,任意节点的值都小于或等于其子节点的值。

3.节点下标间的规律


因为堆是一棵完全二叉树若父节点的下标为i,则左子节点下标为2i+1,右子节点下标为2i+2,这个规律会在算法排序中经常使用。

4.堆的基本操作


上滤(Percolate Up)

上滤是指在堆中插入新元素后,通过一系列的比较和交换操作将该元素上移到合适的位置,以保持堆的堆序性。通常用于最小堆和最大堆中。

步骤:

  1. 将新元素插入到堆的末尾(底部)。
  2. 比较该元素与其父节点的值。
  3. 如果该元素的值比父节点的值更小(对于最小堆)或更大(对于最大堆),则交换它们。
  4. 重复步骤2和步骤3,直到满足堆的性质为止。
下滤(Percolate Down)

下滤是指在删除堆顶元素后,通过一系列的比较和交换操作将堆的最后一个元素(通常是堆底元素)移到堆顶,并将其下移到合适的位置,以保持堆的堆序性。

步骤:

  1. 将堆的最后一个元素(通常是堆底元素)移到堆顶。
  2. 比较该元素与其子节点中较小(对于最小堆)或较大(对于最大堆)的一个。
  3. 如果该元素的值比子节点的值更小(对于最小堆)或更大(对于最大堆),则交换它们。
  4. 重复步骤2和步骤3,直到满足堆的性质为止。
应用场景:
  • 上滤: 通常在插入新元素时使用,确保新元素的插入不破坏堆的性质。
  • 下滤: 通常在删除堆顶元素后使用,以恢复堆的性质。
堆化(Heapify)

堆化(Heapify)是指将一个无序的序列转换成一个堆,可以是最小堆或最大堆。堆化过程可以分为两种:自底向上堆化(Bottom-Up Heapify)和自顶向下堆化(Top-Down Heapify)。

自底向上堆化(Bottom-Up Heapify):

自底向上堆化是从序列的最后一个非叶子节点开始,逐步向前处理每个节点,使得以该节点为根的子树成为一个堆。该方法保证了子树堆化后,整个序列也是一个堆。

步骤:

  1. 从序列的最后一个非叶子节点开始(通常是 n/2-1,其中 n 是序列的长度)。

  2. 对每个非叶子节点,与其子节点比较,如果不满足堆的性质,则进行交换。

  3. 重复上述步骤,直到处理完整个序列。

自顶向下堆化(Top-Down Heapify):

自顶向下堆化是从序列的第一个元素开始,逐步向后处理每个节点,使得以该节点为根的子树成为一个堆。该方法保证了每个节点都满足堆的性质。

步骤:

  1. 从序列的第一个元素开始。

  2. 对每个节点,与其子节点比较,如果不满足堆的性质,则进行交换。

  3. 重复上述步骤,直到处理完整个序列。

应用场景:

  • 建堆: 堆化是建立堆的关键步骤,可以在 O(n) 的时间复杂度内将一个无序序列转化为堆。
  • 堆排序: 在堆排序算法中,首先对待排序序列进行堆化,然后反复取出堆顶元素,直到堆为空,实现排序。
  • 优先队列: 堆被广泛应用于实现优先队列,堆化操作确保队列中优先级最高的元素位于队首。

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

相关文章:

数据结构之<堆>的介绍

1.简介 堆是一种特殊的数据结构,通常用于实现优先队列。堆是一个可以被看作近似完全二叉树的结构,并且具有一些特殊的性质,根据这些性质,堆被分为最大堆(或者大根堆,大顶堆)和最小堆两种。 2.…...

使用Ubuntu22+Minikube快速搭建K8S开发环境

安装Vmware 这一步,可以参考我的如下课程。 安装Ubuntu22 下载ISO镜像 这里我推荐从清华镜像源下载,速度会快非常多。 下载地址:https://mirrors.tuna.tsinghua.edu.cn/ubuntu-releases/22.04.3/ 如果你报名了我的这门视频课程&#xf…...

【中小型企业网络实战案例 二】配置网络互连互通

​【中小型企业网络实战案例 一】规划、需求和基本配置-CSDN博客 热门IT技术视频教程&#xff1a;https://xmws-it.blog.csdn.net/article/details/134398330?spm1001.2014.3001.5502 配置接入层交换机 1.以接入交换机ACC1为例&#xff0c;创建ACC1的业务VLAN 10和20。 <…...

Azure Machine Learning - Azure OpenAI GPT 3.5 Turbo 微调教程

本教程将引导你在Azure平台完成对 gpt-35-turbo-0613 模型的微调。 关注TechLead&#xff0c;分享AI全维度知识。作者拥有10年互联网服务架构、AI产品研发经验、团队管理经验&#xff0c;同济本复旦硕&#xff0c;复旦机器人智能实验室成员&#xff0c;阿里云认证的资深架构师&…...

运维大模型探索之 Text2PromQL 问答机器人

作者&#xff1a;陈昆仪&#xff08;图杨&#xff09; 大家下午好&#xff0c;我是来自阿里云可观测团队的算法工程师陈昆仪。今天分享的主题是“和我交谈并获得您想要的PromQL”。今天我跟大家分享在将AIGC技术运用到可观测领域的探索。 今天分享主要包括5个部分&#xff1a;…...

虚拟机VMware:变动ip修改固定ip

1、配置ip地址 vi /etc/sysconfig/network-scripts/ifcfg-ens33修改为&#xff1a; 修改如下&#xff1a;TYPE"Ethernet" # 网络类型为以太网 BOOTPROTO"static" # 手动分配ip NAME"ens33" # 网卡…...

Docker部署Nexus Maven私服并实现远程访问Nexus界面

&#x1f3ac; 鸽芷咕&#xff1a;个人主页 &#x1f525; 个人专栏: 《linux深造日志》《粉丝福利》 ⛺️生活的理想&#xff0c;就是为了理想的生活! 文章目录 1. Docker安装Nexus2. 本地访问Nexus3. Linux安装Cpolar4. 配置Nexus界面公网地址5. 远程访问 Nexus界面6. 固定N…...

苏州科技大学计算机817程序设计(java) 学习笔记

之前备考苏州科技大学计算机&#xff08;专业课&#xff1a;817程序设计&#xff08;java&#xff09;&#xff09;。 学习Java和算法相关内容&#xff0c;现将笔记及资料统一整理归纳移至这里。 部分内容不太完善&#xff0c;欢迎提议。 目录 考情分析 考卷题型 刷题攻略…...

虚幻学习笔记22—C++同步和异步加载

一、前言 之前提到的静态和动态加载都是同步的加载&#xff0c;同时其中的引用基本都是硬引用。如果资源比较大的话会出现卡顿的现象&#xff0c;下面将介绍一种异步加载的方式。同时&#xff0c;还将介绍一种区别与之前的Load的方法。 在说明同步和异步加载之前需要先讲一下虚…...

华清远见嵌入式学习——ARM——作业3

作业要求&#xff1a; 代码效果图&#xff1a; 代码&#xff1a; led.h #ifndef __LED_H__ #define __LED_H__#define RCC_GPIO (*(unsigned int *)0x50000a28) #define GPIOE_MODER (*(unsigned int *)0x50006000) #define GPIOF_MODER (*(unsigned int *)0x50007000) #defi…...

19.JavaSE

一、JavaSE。 &#xff08;1&#xff09;IO流。 1.字节字符流 2.标准流打印流对象流 &#xff08;2&#xff09;集合。 1.List/Set/Queue/Map集合 2.properties集合 &#xff08;3&#xff09;多线程。 1.线程创建的…...

仓库管理用什么软件

仓库管理是一个非常重要的话题&#xff0c;大到企业&#xff0c;小到个人&#xff0c;只要有货物的往来就会有仓库方面的管理&#xff0c;最为典型的就是货物的进出库存管理&#xff0c;这也是最为基础的仓库管理内容&#xff0c;那么仓库管理要用什么软件&#xff0c;从不同的…...

飞天使-k8s知识点8-kubernetes资源对象-编写中

文章目录 资源对象是k8s核心概念 资源对象是k8s核心概念 查看防火墙规则 32002 端口的去向 [rootkubeadm-master1 ~]# iptables -t nat -vnL |grep 32000 0 KUBE-MARK-MASQ tcp -- * * 0.0.0.0/0 0.0.0.0/0 /* kubernetes-dashboard/…...

Oracle Create user

sqlplus /nolog conn sys/pw123456orcl as sysdba CREATE USER zengwenfeng IDENTIFIED BY zengwenfeng ; GRANT ALL PRIVILEGES TO zengwenfeng ; COMMIT; C:\Users\Administrator>sqlplus /nologSQL*Plus: Release 11.2.0.1.0 Production on 星期日 12月 24 21:38:24 20…...

树莓派,mediapipe,Picamera2利用舵机云台追踪人手(PID控制)

一、项目目标 追踪人手大拇指指尖&#xff1a; 当人手移动时&#xff0c;摄像头通过控制两个伺服电机&#xff08;分别是偏航和俯仰&#xff09;把大拇指指尖放到视界的中心位置&#xff0c;本文采用了PID控制伺服电机 Mediapipe Hand简介 MediaPipe 手部标志任务可检测图像…...

DQL查询数据(超重点)以及distinct(去重)

DQL(Data Query Language:数据查询语言) 1.所有查询操作都用 SELECT 2.无论是简单的查询还是复杂的查询它都能做 3.数据库中最核心的语言&#xff0c;最重要的语句 4.使用频率最高的语句 语法&#xff1a; SELECT 字段1&#xff0c;字段2&#xff0c;……FROM 表 有时候…...

【网络奇缘】——奈氏准则和香农定理从理论到实践一站式服务|计算机网络

&#x1f308;个人主页: Aileen_0v0 &#x1f525;热门专栏: 华为鸿蒙系统学习|计算机网络|数据结构与算法 &#x1f4ab;个人格言:"没有罗马,那就自己创造罗马~" 目录 失真 - 信号的变化 影响信号失真的因素&#xff1a; ​编辑 失真的一种现象&#xff1a;码间…...

MongoDB 根据 _id 获取记录的创建时间并回填记录中

MongoDB 集合 test1,有字段 _id&#xff0c;createTime&#xff0c;createTimeStr&#xff0c;name字段 &#xff0c; 查询createTime不为空的&#xff0c;根据 _id 生成该条记录的创建时间时间戳并填写到字段 createTime 字段中 &#xff0c;并打印时间戳 // 查询 createTime…...

【开源】基于JAVA语言的独居老人物资配送系统

目录 一、摘要1.1 项目介绍1.2 项目录屏 二、功能模块三、系统展示四、核心代码4.1 查询社区4.2 新增物资4.3 查询物资4.4 查询物资配送4.5 新增物资配送 五、免责说明 一、摘要 1.1 项目介绍 基于JAVAVueSpringBootMySQL的独居老人物资配送系统&#xff0c;包含了社区档案、…...

网络7层架构

网络 7 层架构 什么是OSI七层模型&#xff1f; OSI模型用于定义并理解数据从一台计算机转移到另一台计算机&#xff0c;在最基本的形式中&#xff0c;两台计算机通过网线和连接器相互连接&#xff0c;在网卡的帮助下共享数据&#xff0c;形成一个网络&#xff0c;但是一台计算…...

大数据学习栈记——Neo4j的安装与使用

本文介绍图数据库Neofj的安装与使用&#xff0c;操作系统&#xff1a;Ubuntu24.04&#xff0c;Neofj版本&#xff1a;2025.04.0。 Apt安装 Neofj可以进行官网安装&#xff1a;Neo4j Deployment Center - Graph Database & Analytics 我这里安装是添加软件源的方法 最新版…...

云原生核心技术 (7/12): K8s 核心概念白话解读(上):Pod 和 Deployment 究竟是什么?

大家好&#xff0c;欢迎来到《云原生核心技术》系列的第七篇&#xff01; 在上一篇&#xff0c;我们成功地使用 Minikube 或 kind 在自己的电脑上搭建起了一个迷你但功能完备的 Kubernetes 集群。现在&#xff0c;我们就像一个拥有了一块崭新数字土地的农场主&#xff0c;是时…...

超短脉冲激光自聚焦效应

前言与目录 强激光引起自聚焦效应机理 超短脉冲激光在脆性材料内部加工时引起的自聚焦效应&#xff0c;这是一种非线性光学现象&#xff0c;主要涉及光学克尔效应和材料的非线性光学特性。 自聚焦效应可以产生局部的强光场&#xff0c;对材料产生非线性响应&#xff0c;可能…...

React Native 开发环境搭建(全平台详解)

React Native 开发环境搭建&#xff08;全平台详解&#xff09; 在开始使用 React Native 开发移动应用之前&#xff0c;正确设置开发环境是至关重要的一步。本文将为你提供一份全面的指南&#xff0c;涵盖 macOS 和 Windows 平台的配置步骤&#xff0c;如何在 Android 和 iOS…...

2025年能源电力系统与流体力学国际会议 (EPSFD 2025)

2025年能源电力系统与流体力学国际会议&#xff08;EPSFD 2025&#xff09;将于本年度在美丽的杭州盛大召开。作为全球能源、电力系统以及流体力学领域的顶级盛会&#xff0c;EPSFD 2025旨在为来自世界各地的科学家、工程师和研究人员提供一个展示最新研究成果、分享实践经验及…...

sqlserver 根据指定字符 解析拼接字符串

DECLARE LotNo NVARCHAR(50)A,B,C DECLARE xml XML ( SELECT <x> REPLACE(LotNo, ,, </x><x>) </x> ) DECLARE ErrorCode NVARCHAR(50) -- 提取 XML 中的值 SELECT value x.value(., VARCHAR(MAX))…...

在WSL2的Ubuntu镜像中安装Docker

Docker官网链接: https://docs.docker.com/engine/install/ubuntu/ 1、运行以下命令卸载所有冲突的软件包&#xff1a; for pkg in docker.io docker-doc docker-compose docker-compose-v2 podman-docker containerd runc; do sudo apt-get remove $pkg; done2、设置Docker…...

算法:模拟

1.替换所有的问号 1576. 替换所有的问号 - 力扣&#xff08;LeetCode&#xff09; ​遍历字符串​&#xff1a;通过外层循环逐一检查每个字符。​遇到 ? 时处理​&#xff1a; 内层循环遍历小写字母&#xff08;a 到 z&#xff09;。对每个字母检查是否满足&#xff1a; ​与…...

python爬虫——气象数据爬取

一、导入库与全局配置 python 运行 import json import datetime import time import requests from sqlalchemy import create_engine import csv import pandas as pd作用&#xff1a; 引入数据解析、网络请求、时间处理、数据库操作等所需库。requests&#xff1a;发送 …...

关于easyexcel动态下拉选问题处理

前些日子突然碰到一个问题&#xff0c;说是客户的导入文件模版想支持部分导入内容的下拉选&#xff0c;于是我就找了easyexcel官网寻找解决方案&#xff0c;并没有找到合适的方案&#xff0c;没办法只能自己动手并分享出来&#xff0c;针对Java生成Excel下拉菜单时因选项过多导…...