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

【数据结构】核心数据结构之二叉堆的原理及实现

1.大顶堆和小顶堆原理

  • 什么是堆

    • 堆(Heap)是计算机科学中一类特殊的数据结构,通常是一个可以被看作一颗完全二叉树的数组对象。

    • 完全二叉树

      • 只有最下面两层节点的度可以小于2,并且最下层的叶节点集中在靠左连续的边界

      • 只允许最后一层有空缺结点且空缺在右边,完全二叉树需保证最后一个节点之前的节点都齐全;

      • 对任一结点,如果其右子树的深度为j,则其左子树的深度必为j或j+1

在这里插入图片描述

  • 什么是大顶堆(最大堆)
    • 大顶堆是一种完全二叉树,其每个父节点的值都大于或等于其子节点的值,即根节点的值最大。
    • 每个节点的两个子节点顺序没做要求,和之前的二叉查找树不一样。

在这里插入图片描述

  • 什么是小顶堆(最小堆)

    • 小顶堆是一种完全二叉树,其每个父节点的值都小于或等于其子节点的值,即根节点的值最小。

    • 每个节点的两个子节点顺序没做要求,和之前的二叉查找树不一样

在这里插入图片描述

  • 存储原理

    • 一般升序采用大顶堆,降序采用小顶堆。
    • 堆是一种非线性结构,用数组来存储完全二叉树是非常节省空间的,把堆看作一个数组。
      • 方便操作,一般数组的下标0不存储,直接从1节点存储。
    • 堆其实就是利用完全二叉树的结构来维护一个数组
    • 数据下表为k的节点
      • 左子节点下标为2*k的节点。
      • 右子节点就是下表为2*k+1的节点。
      • 父节点就是下标为k/2取证的节点。
  • 公式描述一下堆的定义

    • 大顶堆:arr[k] >= arr[2k+1] && arr[k] >= arr[2k]
    • 小顶堆:arr[k] <= arr[2k+1] && arr[k] <=arr[ak]
  • 小顶堆动画效果演示

  • 往堆中插入新元素,就是往数组中从索引0或1开始依次存放数据,但是顺序需要满足堆的特性

  • 如何让堆满足:
    • 不断比较新节点 arr[k]和对应父节点arr[k/2]的大小,根据情况交互元素位置
    • 直到找到的父节点比当前新增节点大则结束

在这里插入图片描述

2.大顶堆构编码实现

  • 大顶堆(最大堆)

    • 大顶堆是一种完全二叉树,其每个父节点的值都大于或等于其子节点的值,即根节点的值最大

在这里插入图片描述

  • 编码实现
public class Heap {//用数组存储堆中的元素private int[] items;//堆中元素的个数private int num;public Heap(int capacity) {//数组下标0不存储数据,所以容量+1this.items = new int[capacity + 1];this.num = 0;}/*** 判断堆中 items[left] 元素是否小于 items[right] 的元素*/private boolean rightBig(int left, int right) {return items[left] < items[right];}/*** 交换堆中的两个元素位置*/private void swap(int i, int j) {int temp = items[i];items[i] = items[j];items[j] = temp;}/*** 往堆中插入一个元素,默认是最后面,++num先执行,然后进行上浮判断操作*/public void insert(int value) {items[++num] = value;up(num);}/*** 使用上浮操作,新增元素后,重新堆化* 不断比较新节点 arr[k]和对应父节点arr[k/2]的大小,根据情况交互元素位置* 直到找到的父节点比当前新增节点大则结束* <p>* 数组中下标为 k 的节点* 左子节点下标为 2*k 的节点* 右子节点就是下标 为 2*k+1 的节点* 父节点就是下标为 k/2 取整的节点*/private void up(int k) {//父节点 在数组的下标是1,下标大于1都要比较while (k > 1) {//比较 父结点 和 当前结点 大小if (rightBig(k / 2, k)) {//当前节点大,则和父节点交互位置swap(k / 2, k);}// 往上一层比较,当前节点变为父节点k = k / 2;}}/*** 删除堆中最大的元素,返回这个最大元素*/public int delMax() {int max = items[1];//交换索引 堆顶的元素(数组索引1的)和 最大索引处的元素,放到完全二叉树中最右侧的元素,方便后续变为临时根结点// 为啥不能直接删除顶部元素,因为删除后会断裂,成为森林,所以需要先交互,再删除swap(1, num);//最大索引处的元素删除掉, num--是后执行,元素个数需要减少1items[num--] = 0;//通过下浮调整堆,重新堆化down(1);return max;}/*** 使用下沉操作,堆顶和最后一个元素交换后,重新堆化* 不断比较 节点 arr[k]和对应 左节点arr[2*k] 和 右节点arr[2*k+1]的大小,如果当前结点小,则需要交换位置* 直到找到 最后一个索引节点比较完成  则结束* 数组中下标为 k 的节点* 左子节点下标为 2*k 的节点* 右子节点就是下标 为 2*k+1 的节点* 父节点就是下标为 k/2 取整的节点*/private void down(int k) {//最后一个节点下标是numwhile (2 * k <= num) {//记录当前结点的左右子结点中,较大的结点int maxIndex;if (2 * k + 1 <= num) { //2 * k + 1 <= num 是判断 确保有右节点//比较当前结点下的左右子节点哪个大if (rightBig(2 * k, 2 * k + 1)) {maxIndex = 2 * k + 1;} else {maxIndex = 2 * k;}} else {maxIndex = 2 * k;}//比较当前结点 和 较大结点的值, 如果当前节点较大则结束if (items[k] > items[maxIndex]) {break;} else {//否则往下一层比较,当前节点k索引 变换为 子节点中较大的值swap(k, maxIndex);//变换k的值k = maxIndex;}}}public static void main(String[] args) {Heap heap = new Heap(20);heap.insert(42);heap.insert(48);heap.insert(93);heap.insert(21);heap.insert(90);heap.insert(9);heap.insert(3);heap.insert(40);heap.insert(32);int top;System.out.println("输出堆:");while ((top = heap.delMax()) != 0) {System.out.print(top + " ");}}
}

在这里插入图片描述

相关文章:

【数据结构】核心数据结构之二叉堆的原理及实现

1.大顶堆和小顶堆原理 什么是堆 堆&#xff08;Heap&#xff09;是计算机科学中一类特殊的数据结构&#xff0c;通常是一个可以被看作一颗完全二叉树的数组对象。 完全二叉树 只有最下面两层节点的度可以小于2&#xff0c;并且最下层的叶节点集中在靠左连续的边界 只允许最后…...

Spring Cloud Alibaba+saas企业架构技术选型+架构全景业务图 + 架构典型部署方案

基于Spring Cloud Alibaba 分布式微服务高并发数据平台化(中台)思想多租户saas设计的企业开发架构&#xff0c;支持源码二次开发、支持其他业务系统集成、集中式应用权限管理、支持拓展其他任意子项目。 一、架构技术选型 核心框架 Spring Boot SOA Spring Cloud …...

RocketMQ-03

1. 高级功能 1.1 消息存储 分布式队列因为有高可靠性的要求&#xff0c;所以数据要进行持久化存储。 消息生成者发送消息MQ收到消息&#xff0c;将消息进行持久化&#xff0c;在存储中新增一条记录返回ACK给生产者MQ push 消息给对应的消费者&#xff0c;然后等待消费者返回A…...

大神教你在 Linux 中查看你的时区

在这篇短文中&#xff0c;我们将向你简单介绍几种 Linux 下查看系统时区的简单方法。在 Linux 机器中&#xff0c;尤其是生产服务器上的时间管理技能&#xff0c;是在系统管理中一个极其重要的方面。Linux 包含多种可用的时间管理工具&#xff0c;比如 date 或 timedatectlcomm…...

Redis持久化策略

Redis有两种持久化方式:快照(snapshotting,或者叫Redis DataBase,RDB)和只追加文件(append-only,AOF)。两种方式可以单独使用,也可以同时使用。 1.RDB模式 RDB:将某时刻所有数据都写入到硬盘里,存储为.rdb快照文件,新的快照文件生成之后会替换旧的快照文件。用户可以将…...

显著性检验【t-test、方差分析、ks检验】

显著性检验【t-test、方差分析、ks检验】 0、目录 1显著性检验基本定义&#xff08;what&#xff1f;&#xff09; 2.使用显著性检验的意义&#xff08;why? &#xff09; 3.显著性检验的具体操作流程&#xff08;how? &#xff09; 1、显著性检验基本定义 统计假设检验…...

访问学者在德国访学生活衣食住行攻略

德国因其优质的教育水平、高价值的学制、低廉的访学成本&#xff0c;逐渐成为访学领域的宠儿。对于初次来到德国生活的访问学者&#xff0c;一定不是很熟悉德国的真实生活情况。今天51访学网小编就给大家介绍德国访学学衣食住行&#xff0c;希望可以帮助到即将出国的你。 一、…...

SQL-刷题技巧-删除重复记录

一. 原题呈现 牛客 SQL236. 删除emp_no重复的记录&#xff0c;只保留最小的id对应的记录。 描述&#xff1a; 删除emp_no重复的记录&#xff0c;只保留最小的id对应的记录。 drop table if exists titles_test; CREATE TABLE titles_test (id int(11) not null primary key…...

基于JSP的虚拟账号交易平台

技术&#xff1a;Java、JSP等摘要&#xff1a;随着网络游戏以及各种平台的出现与更新&#xff0c;虚拟账号交易平台正逐渐成为电商的新增长点。当今社会&#xff0c;互联网发发展飞速&#xff0c;游戏产业也渐渐兴起&#xff0c;随之虚拟游戏账号的交易量逐渐增多&#xff0c;但…...

LeetCode201_201. 数字范围按位与

LeetCode201_201. 数字范围按位与 一、描述 给你两个整数 left 和 right &#xff0c;表示区间 [left, right] &#xff0c;返回此区间内所有数字 按位与 的结果&#xff08;包含 left 、right 端点&#xff09;。 示例 1&#xff1a; 输入&#xff1a;left 5, right 7 输…...

一款好的风险管理软件可以做什么

风险管理软件哪个好&#xff1f;使用Zoho Projects易于使用的项目风险管理软件&#xff0c;最大限度地减少收入损失并快速调整您的投资组合&#xff0c;保护您的项目投资。Zoho Projects的高级风险管理软件可在您最需要的时候安全的保护您的业务。使用Zoho Projects强大的风险管…...

html2canvas使用文档

一、安装 Install NPM npm install --save html2canvasInstall Yarn yarn add html2canvas二、引入 import html2canvas from html2canvas;三、使用 以 vue 举例&#xff0c;这样写起来比较方便 <div ref"picture"><h4>Hello world!</h4> &l…...

HTML DOM 改变 CSS

HTML DOM 允许 JavaScript 改变 HTML 元素的样式。改变 HTML 样式如需改变 HTML 元素的样式&#xff0c;请使用这个语法&#xff1a;document.getElementById(id).style.propertynew style 下面的例子会改变 <p> 元素的样式&#xff1a;实例<html><body><…...

基于EB工具的TC3xx_MCAL配置开发01_WDG模块配置介绍

目录 1.概述2. WDG 配置2.1 General部分配置2.2 WdgSettingsConfig配置2.2.1 配置概述2.2.2 CPU WDG具体配置2.3 WdgDemEventParameterRefs3. WDG配置注意事项1.概述 本篇开始我们基于EB Tresos工具对英飞凌TC3xx系列MCU的MCAL开发进行介绍,结合项目经验对各MCAL外设的开发及…...

Activty启动到显示的过程[二]

Activity的显示从handleResumeActivity()方法开始。 //ActivityThread.javaOverridepublic void handleResumeActivity(IBinder token, boolean finalStateRequest, boolean isForward,String reason) {final ActivityClientRecord r performResumeActivity(token, finalStat…...

ubuntu 18.04.06LST安装R4.0+版本报错及解决过程

1. sudo apt-get update无法正常使用 错误:13 http://ppa.launchpad.net/webupd8team/sublime-text-3/ubuntu bionic Release 404 Not Found [IP: 2620:2d:4000:1::3e 80] 解决措施&#xff1a;删除 webupd8team/sublime-text-3这个ppa文件。 sudo add-apt-repository --…...

数据湖架构Hudi(五)Hudi集成Flink案例详解

五、Hudi集成Flink案例详解 5.1 hudi集成flink flink的下载地址&#xff1a; https://archive.apache.org/dist/flink/ HudiSupported Flink version0.12.x1.15.x、1.14.x、1.13.x0.11.x1.14.x、1.13.x0.10.x1.13.x0.9.01.12.2 将上述编译好的安装包拷贝到flink下的jars目录…...

【Java学习笔记】9.Java 循环结构 - for, while 及 do...while

Java 循环结构 - for, while 及 do…while 顺序结构的程序语句只能被执行一次。 如果您想要同样的操作执行多次&#xff0c;就需要使用循环结构。 Java中有三种主要的循环结构&#xff1a; while 循环do…while 循环for 循环 在 Java5 中引入了一种主要用于数组的增强型 f…...

【面向对象初步】之面向对象VS面向过程

面向对象(ObjectorientedProgramming,OOP)编程的思想主要是针对大型软件设计而来的。面向对象编程使程序的扩展性更强、可读性更好,使的编程可以像搭积木一样简单。 面向对象编程将数据和操作数据相关的方法封装到对象中,组织代码和数据的方式更加接近人的思维,从而大大提…...

原型链(回顾)

概念prototype__proto__原型链查找机制万物皆对象判断私有/共有属性方法Object.prototype.prototype nullObject.create(proto, [propertiesObject])给类的原型上扩展属性方法的4种方法Fn.prototype.xxx xxxObject.prototype.xxx xxxf1.proto.xxx xxx原型重定向 概念 原型…...

linux之kylin系统nginx的安装

一、nginx的作用 1.可做高性能的web服务器 直接处理静态资源&#xff08;HTML/CSS/图片等&#xff09;&#xff0c;响应速度远超传统服务器类似apache支持高并发连接 2.反向代理服务器 隐藏后端服务器IP地址&#xff0c;提高安全性 3.负载均衡服务器 支持多种策略分发流量…...

MongoDB学习和应用(高效的非关系型数据库)

一丶 MongoDB简介 对于社交类软件的功能&#xff0c;我们需要对它的功能特点进行分析&#xff1a; 数据量会随着用户数增大而增大读多写少价值较低非好友看不到其动态信息地理位置的查询… 针对以上特点进行分析各大存储工具&#xff1a; mysql&#xff1a;关系型数据库&am…...

Objective-C常用命名规范总结

【OC】常用命名规范总结 文章目录 【OC】常用命名规范总结1.类名&#xff08;Class Name)2.协议名&#xff08;Protocol Name)3.方法名&#xff08;Method Name)4.属性名&#xff08;Property Name&#xff09;5.局部变量/实例变量&#xff08;Local / Instance Variables&…...

【大模型RAG】Docker 一键部署 Milvus 完整攻略

本文概要 Milvus 2.5 Stand-alone 版可通过 Docker 在几分钟内完成安装&#xff1b;只需暴露 19530&#xff08;gRPC&#xff09;与 9091&#xff08;HTTP/WebUI&#xff09;两个端口&#xff0c;即可让本地电脑通过 PyMilvus 或浏览器访问远程 Linux 服务器上的 Milvus。下面…...

基于Uniapp开发HarmonyOS 5.0旅游应用技术实践

一、技术选型背景 1.跨平台优势 Uniapp采用Vue.js框架&#xff0c;支持"一次开发&#xff0c;多端部署"&#xff0c;可同步生成HarmonyOS、iOS、Android等多平台应用。 2.鸿蒙特性融合 HarmonyOS 5.0的分布式能力与原子化服务&#xff0c;为旅游应用带来&#xf…...

Keil 中设置 STM32 Flash 和 RAM 地址详解

文章目录 Keil 中设置 STM32 Flash 和 RAM 地址详解一、Flash 和 RAM 配置界面(Target 选项卡)1. IROM1(用于配置 Flash)2. IRAM1(用于配置 RAM)二、链接器设置界面(Linker 选项卡)1. 勾选“Use Memory Layout from Target Dialog”2. 查看链接器参数(如果没有勾选上面…...

python执行测试用例,allure报乱码且未成功生成报告

allure执行测试用例时显示乱码&#xff1a;‘allure’ &#xfffd;&#xfffd;&#xfffd;&#xfffd;&#xfffd;ڲ&#xfffd;&#xfffd;&#xfffd;&#xfffd;ⲿ&#xfffd;&#xfffd;&#xfffd;Ҳ&#xfffd;&#xfffd;&#xfffd;ǿ&#xfffd;&am…...

深度学习水论文:mamba+图像增强

&#x1f9c0;当前视觉领域对高效长序列建模需求激增&#xff0c;对Mamba图像增强这方向的研究自然也逐渐火热。原因在于其高效长程建模&#xff0c;以及动态计算优势&#xff0c;在图像质量提升和细节恢复方面有难以替代的作用。 &#x1f9c0;因此短时间内&#xff0c;就有不…...

【C++进阶篇】智能指针

C内存管理终极指南&#xff1a;智能指针从入门到源码剖析 一. 智能指针1.1 auto_ptr1.2 unique_ptr1.3 shared_ptr1.4 make_shared 二. 原理三. shared_ptr循环引用问题三. 线程安全问题四. 内存泄漏4.1 什么是内存泄漏4.2 危害4.3 避免内存泄漏 五. 最后 一. 智能指针 智能指…...

【LeetCode】算法详解#6 ---除自身以外数组的乘积

1.题目介绍 给定一个整数数组 nums&#xff0c;返回 数组 answer &#xff0c;其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 不要使用除法&#xff0c;且在 O…...