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

数据结构之二叉树——堆 详解(含代码实现)

1.堆

如果有一个关键码的集合 K = { , , , ,},把它的所有元素按完全二叉树的顺序存储方式存储
在一个一维数组中,则称为小堆( 或大堆 ) 。将根节点最大的堆叫做最大堆或大根堆,根节点最小的堆叫做最小堆或小根堆。

堆的性质:

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

创建堆

向上调整建堆

向下调整建堆

堆的插入

先插入一个10到数组的尾上,再进行向上调整算法,直到满足堆

向上调整算法

数组一个个循环插入时边插入边成堆,当插入新的元素时向上调整成新的堆

使用向上调整算法,每次孩子与父亲相比较,当孩子大于或小于父亲时进行交换,改变孩子的下标,再次进行判断然后交换,知道孩子的下标为0

堆的删除

向下调整算法

给出一个数组,逻辑上看做一颗完全二叉树。通过从根节点开始的向下调整算法可以把它调整成一个小堆。向下调整算法有一个前提:左右子树必须是一个堆,才能调整。

当已经成大堆或者小堆后想删元素,最好的办法是把堆的第一个元素与最后一个进行交换,当交换完成,堆中最大或最小的元素就到了最后一个结点,减小下标进行删除,此时堆顶的左右子树为大堆或者小堆,用向下调整算法,将父亲与孩子循环比较大小进行交换,形成新的堆,再次把堆顶元素与最后一个元素交换,使用向下调整成新的堆,反复进行即可删除堆

堆的排序   升序  降序

向上调整建堆,堆顶元素与最后一个元素交换,再次向上或向下调整,得到升序或降序

向上调整建堆

向下调整建堆

向上向下调整对比

向下调整时间复杂度分析

向上调整时间复杂度分析

总结

堆排序时间复杂度

堆的代码实现

//头文件
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>typedef int HPDataType;
typedef struct Heap
{HPDataType* a;int size;int capacity;
}Heap;
//初始化
void HeapInit(Heap* hp);
// 堆的销毁
void HeapDestory(Heap* hp);
// 堆的插入
void HeapPush(Heap* hp, HPDataType x);
// 堆的删除
void HeapPop(Heap* hp);
// 取堆顶的数据
HPDataType HeapTop(Heap* hp);
// 堆的数据个数
int HeapSize(Heap* hp);
// 堆的判空
bool HeapEmpty(Heap* hp);
//向上调整
void Adjustup(HPDataType* a, int child);
//向下调整
void Adjustdown(HPDataType* a, int parent);
void swap(Heap* hp, int child, int parent);
//函数实现
#define _CRT_SECURE_NO_WARNINGS  1
#pragma warning(disable:6031)
#include"heap.h"
//初始化
void HeapInit(Heap* hp)
{assert(hp);hp->a = NULL;hp->size = hp->capacity = 0;
}
void swap( int *p1, int *p2)
{int tmp = *p1;*p1 = *p2;*p2 = tmp;
}
bool HeapEmpty(Heap* hp)
{assert(hp);return hp->size == 0;
}// 堆的销毁
void HeapDestory(Heap* hp)
{free(hp->a);hp->a = NULL;free(hp);hp = NULL;
}
//向上调整
void Adjustup(HPDataType* a, int child)
{assert(a);int parent = (child - 1) / 2;while (child > 0){if (a[child] < a[parent]){swap(&a[child], &a[parent]);child = parent;parent = (child - 1) / 2;}else {break;}}
}
// 堆的插入
void HeapPush(Heap* hp, HPDataType x)
{assert(hp);if (hp->capacity == hp->size)//1未开劈空间 2.已满没有空间{int newcapacity = hp->capacity == 0 ? 4 : hp->capacity * 2;Heap* tmp = (Heap*)realloc(hp->a, sizeof(HPDataType)* newcapacity);if (tmp == NULL){perror("realloc fail");return NULL;}hp->a = tmp;hp->capacity = newcapacity;}//空间够  hp->a[hp->size] = x;hp->size++;//放进之后 向上调整形成新的堆Adjustup(hp->a, hp->size - 1);
}
//向xia调整
void Adjustdown(HPDataType* a,int n, int parent)
{assert(a);int child = parent * 2 + 1;while (child < n){     //右孩子小于huo大于左孩子if (child + 1 < n && a[child + 1] < a[child]){child++;}if (a[parent] > a[child]){swap(&a[child], &a[parent]);parent = child;child= parent * 2 + 1;}else {break;}}
}
// 堆的删除
void HeapPop(Heap* hp)
{assert(hp);assert(!HeapEmpty(hp));//把第一个元素与最后一个交换,向下调整swap( &hp->a[0],&hp->a[hp->size-1]);hp->size--;Adjustdown(hp->a, hp->size, 0);}
//取堆顶数据
HPDataType HeapTop(Heap* hp)
{assert(hp);assert(!HeapEmpty(hp));return hp->a[0];
}
// 堆的数据个数
int HeapSize(Heap* hp)
{assert(hp);return hp->size;
}
#define _CRT_SECURE_NO_WARNINGS  1
#pragma warning(disable:6031)
#include"heap.h"
void test()
{Heap hp;HeapInit(&hp);int a[] = { 60,50,6,8,14,7,3 };for (int i = 0; i < sizeof(a) / sizeof(a[0]); i++){HeapPush(&hp, a[i]);}HeapDestroy(&hp);
}
void HeapSort(int* a, int n)
{// 升序 -- 建大堆// 降序 -- 建小堆Heap hp;HeapInit(&hp);//建堆--向上调整建堆/*for (int i = 1; i < n; i++){AdjustUp(a, i);}*/// 建堆--向下调整建堆 --O(N)for (int i = (n - 1 - 1) / 2; i >= 0; --i){AdjustDown(a, n, i);}int end = n - 1;while (end > 0){Swap(&a[0], &a[end]);// 再调整,选出次小的数AdjustDown(a, end, 0);--end;}
}
int main()
{test();return 0;
}

相关文章:

数据结构之二叉树——堆 详解(含代码实现)

1.堆 如果有一个关键码的集合 K { &#xff0c; &#xff0c; &#xff0c; … &#xff0c;}&#xff0c;把它的所有元素按完全二叉树的顺序存储方式存储 在一个一维数组中&#xff0c;则称为小堆( 或大堆 ) 。将根节点最大的堆叫做最大堆或大根堆&#xff0c;根节点最小的…...

推荐一款面向增材制造的高效设计平台:nTopology

nTopology是一款面向增材制造的高效设计平台&#xff0c;平台预置了大量增材制造常用的设计工具包&#xff0c;工程师通过调用若干个预置工具包、或自主开发定制的工具包&#xff0c;建立一个工作流&#xff0c;实现复杂几何结构的参数化设计。nTopology集合了的强大几何建模和…...

SQL,力扣题目1767,寻找没有被执行的任务对【递归】

一、力扣链接 LeetCode_1767 二、题目描述 表&#xff1a;Tasks ------------------------- | Column Name | Type | ------------------------- | task_id | int | | subtasks_count | int | ------------------------- task_id 具有唯一值的列。 ta…...

JavaScript数据类型- Symbol 详解

文章目录 前言1.唯一性2. 描述3. 作为对象属性键4. 全局注册6. 不可变性7. 隐式转换 前言 Symbol是ES6新增内容&#xff0c;代表创建后独一无二且不可变的数据类型&#xff0c;它主要是为了解决可能出现的全局变量冲突的问题 在JavaScript发展的过程中&#xff0c;其中的ES6带…...

WordPress网站添加嵌入B站视频,自适应屏幕大小,取消自动播放

结合bv号 改成以下嵌入式代码&#xff08;自适应屏幕大小,取消自动播放&#xff09; <iframe style"width: 100%; aspect-ratio: 16/9;" src"//player.bilibili.com/player.html?isOutsidetrue&bvidBV13CSVYREpr&p1&autoplay0" scrolling…...

11.6 校内模拟赛总结

打的很顺的一场 复盘 7:40 开题&#xff0c;看到题目名很interesting T1 看起来很典&#xff0c;中位数显然考虑二分&#xff0c;然后就是最大子段和&#xff1b;T2 构造&#xff1f;一看数据范围这么小&#xff0c;感觉不是很难做&#xff1b;T3 神秘数据结构&#xff1b;T…...

Redis常用的五大数据类型(列表List,集合set)

简介 List 的特点&#xff1a;单键多值。底层实际是个双向链表&#xff0c;对两端的操作性能很高&#xff0c;通过索引下标的操作中间的节点性能会较差。 Redis 列表是简单的字符串列表&#xff0c;按照插入顺序排序。你可以添加一个元素到列表的头部&#xff08;左边&#xff…...

Ubuntu 20.04 部署向量数据库 Milvus + Attu

前言 最开始在自己的办公电脑&#xff08;无显卡的 windows 10 系统&#xff09; 上使用 Docker Desktop 部署了 Milvus 容器&#xff0c;方便的很&#xff0c; 下载 Attu 也很方便&#xff0c;直接就把这个向量数据库通过 Attu 这个图形化界面跑了起来&#xff0c;使用起来感…...

实现数传数据转网口(以太网)和遥控器SBUS信号转串口的功能

为了帮助你实现数传数据转网口&#xff08;以太网&#xff09;和SBUS信号转串口的功能&#xff0c;这里提供一个基本的框架。我们将使用STM32微控制器来完成这些任务。假设你已经具备了STM32的基本开发经验&#xff0c;并且已经安装了相应的开发环境&#xff08;如STM32CubeIDE…...

APP 后台广告位配置的关键要素与策略

在当今数字化营销的浪潮中&#xff0c;APP 作为重要的信息传播渠道&#xff0c;其后台广告位的配置显得尤为关键。这不仅影响着广告的展示效果&#xff0c;还直接关系到用户体验和平台收益。 首先&#xff0c;了解目标受众是配置广告位的基础。通过对 APP 用户的行为数据进行分…...

分布式数据库概述

分布式数据库概述 分布式数据库是一种将数据分散存储在多个物理节点上的数据库系统,这些节点通过网络相互连接,形成一个逻辑上统一的数据库系统。它旨在提高数据的可用性、可靠性、性能和可扩展性,是现代大数据和云计算环境下不可或缺的重要技术。 一、分布式数据库的核心…...

用通义灵码帮助实现校验bpmn.js当前画布上只能有一个开始节点的功能

最终代码&#xff1a; const elementRegistry this.bpmnModeler.get(elementRegistry);// 获取所有元素const allElements elementRegistry.getAll();// 过滤出开始节点const startEvents allElements.filter(element > element.type bpmn:StartEvent);// 校验开始节点的…...

OKHTTP断点续传

OKHTTP断点续传 文章目录 OKHTTP断点续传HTTP断点续传知识点RangeContent RangeEtag&If-Range&#xff08;文件唯一标志&#xff09; OKHTTP断点下载OKHTTP 简单短断点下载代码示例 Android 断点续传一直是面试的高频问点&#xff0c;这里从HTTP断点续传知识和Android续传思…...

软件测试学习笔记丨Flask操作数据库-ORM

本文转自测试人社区&#xff0c;原文链接&#xff1a;https://ceshiren.com/t/topic/23426 什么是持久化 是把数据保存到可永久保存的存储设备中&#xff08;比如磁盘&#xff09;。持久化的主要应用是将内存中的数据存储在关系型数据库中&#xff0c;当然也可以存储在磁盘文件…...

ABAP 开发的那些小技巧

在对话框程序中的选择屏幕添加图标 要在选择屏幕中添加图标&#xff0c;其中包括参数&#xff1a; 在参数的选择文本中或选择选项(select-option)中写入 01 或选择选项&#xff1a; 您可以使用 01、02、03&#xff0c;依此类推&#xff0c;以获取不同的不同图标。 在运行时…...

电科金仓(人大金仓)更新授权文件(致命错误: XX000: License file expired.)

问题:电科金仓(人大金仓)数据库链接异常,重启失败,查看日志如下: 致命错误: XX000: License file expired. 位置: PostmasterMain, postmaster.c:725 解决方法: 一、下载授权文件 根据安装版本在官网下载授权文件(电科金仓-成为世界卓越的数据库产品与服务提供商)…...

玩转「HF/魔搭/魔乐」平台

模型下载 Hugging Face 下载到 GitHub CodeSpace CodeSpace创建环境&#xff1a; # 安装transformers pip install transformers4.38 pip install sentencepiece0.1.99 pip install einops0.8.0 pip install protobuf5.27.2 pip install accelerate0.33.0下载internlm2_5-7b…...

鸿蒙系统的优势 开发 环境搭建 开发小示例

HarmonyOS是面向多智能终端、全场景的分布式操作系统,为消费者提供跨终端的无缝体验.华为开发者联盟从HarmonyOS应用设计、开发、测试、推广变现等环节全方位助力开发者。 开发者可以通过以下步骤学习鸿蒙系统的开发&#xff1a; 基础理论学习&#xff1a; 了解鸿蒙系统概述&a…...

python批量合并excel文件

当工作中发现有多个excel表需要进行相同的操作或者需要汇总在一起&#xff0c;一个一个处理太费时间&#xff0c;以下的python代码能够帮你解决这个问题~ import pandas as pd import os# 设置Excel文件所在的文件夹路径和合并文件的输出路径 folder_path D:\\Desktop\\dat…...

AWS S3 JavaScript SDK(v3)常用操作

安装 aws s3 sdk npm install aws-sdk/client-s3配置 创建 ~/.aws/credentials 文件&#xff0c;添加以下配置项&#xff1a; [default] aws_access_key_id<...> aws_secret_access_key<...> region<...>S3 SDK常用桶操作 获取桶列表 import {S3Client,…...

css实现圆环展示百分比,根据值动态展示所占比例

代码如下 <view class""><view class"circle-chart"><view v-if"!!num" class"pie-item" :style"{background: conic-gradient(var(--one-color) 0%,#E9E6F1 ${num}%),}"></view><view v-else …...

8k长序列建模,蛋白质语言模型Prot42仅利用目标蛋白序列即可生成高亲和力结合剂

蛋白质结合剂&#xff08;如抗体、抑制肽&#xff09;在疾病诊断、成像分析及靶向药物递送等关键场景中发挥着不可替代的作用。传统上&#xff0c;高特异性蛋白质结合剂的开发高度依赖噬菌体展示、定向进化等实验技术&#xff0c;但这类方法普遍面临资源消耗巨大、研发周期冗长…...

基于服务器使用 apt 安装、配置 Nginx

&#x1f9fe; 一、查看可安装的 Nginx 版本 首先&#xff0c;你可以运行以下命令查看可用版本&#xff1a; apt-cache madison nginx-core输出示例&#xff1a; nginx-core | 1.18.0-6ubuntu14.6 | http://archive.ubuntu.com/ubuntu focal-updates/main amd64 Packages ng…...

关于iview组件中使用 table , 绑定序号分页后序号从1开始的解决方案

问题描述&#xff1a;iview使用table 中type: "index",分页之后 &#xff0c;索引还是从1开始&#xff0c;试过绑定后台返回数据的id, 这种方法可行&#xff0c;就是后台返回数据的每个页面id都不完全是按照从1开始的升序&#xff0c;因此百度了下&#xff0c;找到了…...

MODBUS TCP转CANopen 技术赋能高效协同作业

在现代工业自动化领域&#xff0c;MODBUS TCP和CANopen两种通讯协议因其稳定性和高效性被广泛应用于各种设备和系统中。而随着科技的不断进步&#xff0c;这两种通讯协议也正在被逐步融合&#xff0c;形成了一种新型的通讯方式——开疆智能MODBUS TCP转CANopen网关KJ-TCPC-CANP…...

解决本地部署 SmolVLM2 大语言模型运行 flash-attn 报错

出现的问题 安装 flash-attn 会一直卡在 build 那一步或者运行报错 解决办法 是因为你安装的 flash-attn 版本没有对应上&#xff0c;所以报错&#xff0c;到 https://github.com/Dao-AILab/flash-attention/releases 下载对应版本&#xff0c;cu、torch、cp 的版本一定要对…...

工业自动化时代的精准装配革新:迁移科技3D视觉系统如何重塑机器人定位装配

AI3D视觉的工业赋能者 迁移科技成立于2017年&#xff0c;作为行业领先的3D工业相机及视觉系统供应商&#xff0c;累计完成数亿元融资。其核心技术覆盖硬件设计、算法优化及软件集成&#xff0c;通过稳定、易用、高回报的AI3D视觉系统&#xff0c;为汽车、新能源、金属制造等行…...

.Net Framework 4/C# 关键字(非常用,持续更新...)

一、is 关键字 is 关键字用于检查对象是否于给定类型兼容,如果兼容将返回 true,如果不兼容则返回 false,在进行类型转换前,可以先使用 is 关键字判断对象是否与指定类型兼容,如果兼容才进行转换,这样的转换是安全的。 例如有:首先创建一个字符串对象,然后将字符串对象隐…...

JavaScript基础-API 和 Web API

在学习JavaScript的过程中&#xff0c;理解API&#xff08;应用程序接口&#xff09;和Web API的概念及其应用是非常重要的。这些工具极大地扩展了JavaScript的功能&#xff0c;使得开发者能够创建出功能丰富、交互性强的Web应用程序。本文将深入探讨JavaScript中的API与Web AP…...

【JVM面试篇】高频八股汇总——类加载和类加载器

目录 1. 讲一下类加载过程&#xff1f; 2. Java创建对象的过程&#xff1f; 3. 对象的生命周期&#xff1f; 4. 类加载器有哪些&#xff1f; 5. 双亲委派模型的作用&#xff08;好处&#xff09;&#xff1f; 6. 讲一下类的加载和双亲委派原则&#xff1f; 7. 双亲委派模…...