数据结构之二叉树——堆 详解(含代码实现)
1.堆
堆的性质:
创建堆
向上调整建堆

向下调整建堆

堆的插入
向上调整算法
数组一个个循环插入时边插入边成堆,当插入新的元素时向上调整成新的堆
使用向上调整算法,每次孩子与父亲相比较,当孩子大于或小于父亲时进行交换,改变孩子的下标,再次进行判断然后交换,知道孩子的下标为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 { , , , … ,},把它的所有元素按完全二叉树的顺序存储方式存储 在一个一维数组中,则称为小堆( 或大堆 ) 。将根节点最大的堆叫做最大堆或大根堆,根节点最小的…...
推荐一款面向增材制造的高效设计平台:nTopology
nTopology是一款面向增材制造的高效设计平台,平台预置了大量增材制造常用的设计工具包,工程师通过调用若干个预置工具包、或自主开发定制的工具包,建立一个工作流,实现复杂几何结构的参数化设计。nTopology集合了的强大几何建模和…...
SQL,力扣题目1767,寻找没有被执行的任务对【递归】
一、力扣链接 LeetCode_1767 二、题目描述 表:Tasks ------------------------- | Column Name | Type | ------------------------- | task_id | int | | subtasks_count | int | ------------------------- task_id 具有唯一值的列。 ta…...
JavaScript数据类型- Symbol 详解
文章目录 前言1.唯一性2. 描述3. 作为对象属性键4. 全局注册6. 不可变性7. 隐式转换 前言 Symbol是ES6新增内容,代表创建后独一无二且不可变的数据类型,它主要是为了解决可能出现的全局变量冲突的问题 在JavaScript发展的过程中,其中的ES6带…...
WordPress网站添加嵌入B站视频,自适应屏幕大小,取消自动播放
结合bv号 改成以下嵌入式代码(自适应屏幕大小,取消自动播放) <iframe style"width: 100%; aspect-ratio: 16/9;" src"//player.bilibili.com/player.html?isOutsidetrue&bvidBV13CSVYREpr&p1&autoplay0" scrolling…...
11.6 校内模拟赛总结
打的很顺的一场 复盘 7:40 开题,看到题目名很interesting T1 看起来很典,中位数显然考虑二分,然后就是最大子段和;T2 构造?一看数据范围这么小,感觉不是很难做;T3 神秘数据结构;T…...
Redis常用的五大数据类型(列表List,集合set)
简介 List 的特点:单键多值。底层实际是个双向链表,对两端的操作性能很高,通过索引下标的操作中间的节点性能会较差。 Redis 列表是简单的字符串列表,按照插入顺序排序。你可以添加一个元素到列表的头部(左边ÿ…...
Ubuntu 20.04 部署向量数据库 Milvus + Attu
前言 最开始在自己的办公电脑(无显卡的 windows 10 系统) 上使用 Docker Desktop 部署了 Milvus 容器,方便的很, 下载 Attu 也很方便,直接就把这个向量数据库通过 Attu 这个图形化界面跑了起来,使用起来感…...
实现数传数据转网口(以太网)和遥控器SBUS信号转串口的功能
为了帮助你实现数传数据转网口(以太网)和SBUS信号转串口的功能,这里提供一个基本的框架。我们将使用STM32微控制器来完成这些任务。假设你已经具备了STM32的基本开发经验,并且已经安装了相应的开发环境(如STM32CubeIDE…...
APP 后台广告位配置的关键要素与策略
在当今数字化营销的浪潮中,APP 作为重要的信息传播渠道,其后台广告位的配置显得尤为关键。这不仅影响着广告的展示效果,还直接关系到用户体验和平台收益。 首先,了解目标受众是配置广告位的基础。通过对 APP 用户的行为数据进行分…...
分布式数据库概述
分布式数据库概述 分布式数据库是一种将数据分散存储在多个物理节点上的数据库系统,这些节点通过网络相互连接,形成一个逻辑上统一的数据库系统。它旨在提高数据的可用性、可靠性、性能和可扩展性,是现代大数据和云计算环境下不可或缺的重要技术。 一、分布式数据库的核心…...
用通义灵码帮助实现校验bpmn.js当前画布上只能有一个开始节点的功能
最终代码: 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(文件唯一标志) OKHTTP断点下载OKHTTP 简单短断点下载代码示例 Android 断点续传一直是面试的高频问点,这里从HTTP断点续传知识和Android续传思…...
软件测试学习笔记丨Flask操作数据库-ORM
本文转自测试人社区,原文链接:https://ceshiren.com/t/topic/23426 什么是持久化 是把数据保存到可永久保存的存储设备中(比如磁盘)。持久化的主要应用是将内存中的数据存储在关系型数据库中,当然也可以存储在磁盘文件…...
ABAP 开发的那些小技巧
在对话框程序中的选择屏幕添加图标 要在选择屏幕中添加图标,其中包括参数: 在参数的选择文本中或选择选项(select-option)中写入 01 或选择选项: 您可以使用 01、02、03,依此类推,以获取不同的不同图标。 在运行时…...
电科金仓(人大金仓)更新授权文件(致命错误: XX000: License file expired.)
问题:电科金仓(人大金仓)数据库链接异常,重启失败,查看日志如下: 致命错误: XX000: License file expired. 位置: PostmasterMain, postmaster.c:725 解决方法: 一、下载授权文件 根据安装版本在官网下载授权文件(电科金仓-成为世界卓越的数据库产品与服务提供商)…...
玩转「HF/魔搭/魔乐」平台
模型下载 Hugging Face 下载到 GitHub CodeSpace CodeSpace创建环境: # 安装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应用设计、开发、测试、推广变现等环节全方位助力开发者。 开发者可以通过以下步骤学习鸿蒙系统的开发: 基础理论学习: 了解鸿蒙系统概述&a…...
python批量合并excel文件
当工作中发现有多个excel表需要进行相同的操作或者需要汇总在一起,一个一个处理太费时间,以下的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 文件,添加以下配置项: [default] aws_access_key_id<...> aws_secret_access_key<...> region<...>S3 SDK常用桶操作 获取桶列表 import {S3Client,…...
将对透视变换后的图像使用Otsu进行阈值化,来分离黑色和白色像素。这句话中的Otsu是什么意思?
Otsu 是一种自动阈值化方法,用于将图像分割为前景和背景。它通过最小化图像的类内方差或等价地最大化类间方差来选择最佳阈值。这种方法特别适用于图像的二值化处理,能够自动确定一个阈值,将图像中的像素分为黑色和白色两类。 Otsu 方法的原…...
中医有效性探讨
文章目录 西医是如何发展到以生物化学为药理基础的现代医学?传统医学奠基期(远古 - 17 世纪)近代医学转型期(17 世纪 - 19 世纪末)现代医学成熟期(20世纪至今) 中医的源远流长和一脉相承远古至…...
《C++ 模板》
目录 函数模板 类模板 非类型模板参数 模板特化 函数模板特化 类模板的特化 模板,就像一个模具,里面可以将不同类型的材料做成一个形状,其分为函数模板和类模板。 函数模板 函数模板可以简化函数重载的代码。格式:templa…...
初探Service服务发现机制
1.Service简介 Service是将运行在一组Pod上的应用程序发布为网络服务的抽象方法。 主要功能:服务发现和负载均衡。 Service类型的包括ClusterIP类型、NodePort类型、LoadBalancer类型、ExternalName类型 2.Endpoints简介 Endpoints是一种Kubernetes资源…...
JVM虚拟机:内存结构、垃圾回收、性能优化
1、JVM虚拟机的简介 Java 虚拟机(Java Virtual Machine 简称:JVM)是运行所有 Java 程序的抽象计算机,是 Java 语言的运行环境,实现了 Java 程序的跨平台特性。JVM 屏蔽了与具体操作系统平台相关的信息,使得 Java 程序只需生成在 JVM 上运行的目标代码(字节码),就可以…...
【电力电子】基于STM32F103C8T6单片机双极性SPWM逆变(硬件篇)
本项目是基于 STM32F103C8T6 微控制器的 SPWM(正弦脉宽调制)电源模块,能够生成可调频率和幅值的正弦波交流电源输出。该项目适用于逆变器、UPS电源、变频器等应用场景。 供电电源 输入电压采集 上图为本设计的电源电路,图中 D1 为二极管, 其目的是防止正负极电源反接, …...
【无标题】路径问题的革命性重构:基于二维拓扑收缩色动力学模型的零点隧穿理论
路径问题的革命性重构:基于二维拓扑收缩色动力学模型的零点隧穿理论 一、传统路径模型的根本缺陷 在经典正方形路径问题中(图1): mermaid graph LR A((A)) --- B((B)) B --- C((C)) C --- D((D)) D --- A A -.- C[无直接路径] B -…...
Ubuntu系统多网卡多相机IP设置方法
目录 1、硬件情况 2、如何设置网卡和相机IP 2.1 万兆网卡连接交换机,交换机再连相机 2.1.1 网卡设置 2.1.2 相机设置 2.3 万兆网卡直连相机 1、硬件情况 2个网卡n个相机 电脑系统信息,系统版本:Ubuntu22.04.5 LTS;内核版本…...
Unity VR/MR开发-VR开发与传统3D开发的差异
视频讲解链接:【XR马斯维】VR/MR开发与传统3D开发的差异【UnityVR/MR开发教程--入门】_哔哩哔哩_bilibili...
车载诊断架构 --- ZEVonUDS(J1979-3)简介第一篇
我是穿拖鞋的汉子,魔都中坚持长期主义的汽车电子工程师。 老规矩,分享一段喜欢的文字,避免自己成为高知识低文化的工程师: 做到欲望极简,了解自己的真实欲望,不受外在潮流的影响,不盲从,不跟风。把自己的精力全部用在自己。一是去掉多余,凡事找规律,基础是诚信;二是…...
