数据结构 | 详解二叉树——堆与堆排序
🥝堆
大堆:父节点总是大于子节点。

小堆:父节点总是小于子节点。

注意:1.同一个节点下的两个子节点并无要求先后顺序。
2.堆可以是无序的。
🍉堆的实现
🌴深度剖析
1.父节点和子节点之间的关系
子节点=(父节点*2)+1
或者子节点=(父节点*2)+2
父节点=(子节点-1)/2
2.堆的插入HeapPush实现
void HeapPush(Heap* php, HPDataType x) {assert(php);if (php->size == php->capacity) {int newcapacity = 0 ? 4 : 2 * php->capacity;HPDataType* tmp = (HPDataType*)malloc(sizeof(HPDataType) * newcapacity);if (tmp == NULL) {perror("malloc fail!");}php->a = tmp;php->capacity = newcapacity;}php->a[php->size] = x;AdjustUp(php->a,php->size);php->size++;
}
3.堆的删除HeapPop函数的实现
函数目的:删除堆顶元素
为了避免破坏堆的整体结构,先将首尾元素进行交换,再对首元素进行向下调整,直到满足堆。最后php->size--即可删除原栈顶元素。
void HeapPop(Heap* php) {assert(php);swap(&php->a[0], &php->a[php->size - 1]);AdjustDown(php->a, php->size,0);php->size--;
}
🥳代码实现
Heap.h
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
typedef int HPDataType;
typedef struct Heap
{HPDataType* a;int size;int capacity;
}Heap;void HeapInit(Heap* php);
// 堆的销毁
void HeapDestory(Heap* php);
// 堆的插入
void HeapPush(Heap* php, HPDataType x);
// 堆的删除
void HeapPop(Heap* php);
// 取堆顶的数据
HPDataType HeapTop(Heap* php);
// 堆的数据个数
int HeapSize(Heap* php);
// 堆的判空
int HeapEmpty(Heap* php);
Heap.c
#define _CRT_SECURE_NO_WARNINGS
#include "Heap.h"
void HeapInit(Heap* php) {assert(php);php->a = NULL;php->capacity = php->size = 0;
}void HeapDestory(Heap* php) {assert(php);free(php->a);php->a = NULL;php->capacity = php->size = 0;
}void swap(int* a, int* b) {int tmp = *a;*a= *b;*b = tmp;
}
//小堆
void AdjustUp(HPDataType* a,int child) {assert(a);int parent = (child - 1) / 2;while (child > 0) {if (a[parent] > a[child]) {swap(&a[parent], &a[child]);child = parent;parent = (child - 1) / 2;}else {break;}}
}void HeapPush(Heap* php, HPDataType x) {assert(php);if (php->size == php->capacity) {int newcapacity = 0 ? 4 : 2 * php->capacity;HPDataType* tmp = (HPDataType*)malloc(sizeof(HPDataType) * newcapacity);if (tmp == NULL) {perror("malloc fail!");}php->a = tmp;php->capacity = newcapacity;}php->a[php->size] = x;AdjustUp(php->a,php->size);php->size++;
}
//从给定的子节点开始,不断向上与其父节点进行比较和可能的交换,直到达到根节点或找到一个满足最大堆性质的父节点为止。
void AdjustDown(int* a, int n, int parent) {assert(a);int child = parent * 2 + 1;while (child < n) {if (child + 1 < n && a[child] < a[child + 1]) {child++;}if (a[parent] < a[child]) {swap(&a[parent], &a[child]);parent = child;child = parent * 2 + 1;}else {break;}}
}void HeapPop(Heap* php) {assert(php);swap(&php->a[0], &php->a[php->size - 1]);AdjustDown(php->a, php->size,0);php->size--;
}HPDataType HeapTop(Heap* php) {assert(php);assert(php->size > 0);return php->a[0];
}int HeapSize(Heap* php) {assert(php);return php->size;
}int HeapEmpty(Heap* php) {assert(php);return php->size;
}
test.c
#define _CRT_SECURE_NO_WARNINGS
#include "Heap.h"
int main() {Heap hp;HeapInit(&hp);HeapPush(&hp, 7);HeapPush(&hp, 6);HeapPush(&hp, 5);HeapPush(&hp, 4);HeapPush(&hp, 3);HeapPush(&hp, 2);HeapPush(&hp, 1);for (int i = 0; i < hp.size; i++) {printf("%d ", hp.a[i]);}HeapPop(&hp);printf("\n");for (int i = 0; i < hp.size; i++) {printf("%d ", hp.a[i]);}printf("\n");printf("堆顶元素为%d\n", HeapTop(&hp));if (HeapEmpty(&hp)) {printf("堆不为空\n");}else {printf("堆为空\n");}return 0;
}
🍇堆排序
🌴深度剖析
第一步:建堆
(升序建大堆,降序建小堆)
以升序为例:
从最后一个父节点开始向前遍历,向上调整(大的上小的下)。

//建堆:从倒数第一个父节点开始向前遍历,向下调整for (int i = (n-1-1)/2; i >=0 ;i--) {AdjustDown(a,n,i);}
第二步:排序
1.首尾元素交换(左图)
2.再向下调整(大的上小的下),这样调整后的堆顶元素必为调整范围内的最大值,经过下一轮的首尾元素交换后,就可以放入调整完的区域内。



while (n - 1) {swap(&a[0], &a[n - 1]);AdjustDown(a, n-1,0);n--;
🥳代码实现
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <assert.h>void swap(int* a, int* b) {int tmp = *a;*a = *b;*b = tmp;
}void AdjustUp(int* a, int child) {assert(a);int parent = (child - 1) / 2;while (child > 0) {if (a[parent] < a[child]) {swap(&a[parent], &a[child]);child = parent;parent = (child - 1) / 2;}else {break;}}
}
void AdjustDown(int* a, int n, int parent) {assert(a);int child = parent * 2 + 1;while (child < n ) {if (child + 1 < n && a[child] < a[child + 1]) {child++;}if (a[parent] < a[child]) {swap(&a[parent], &a[child]);parent = child;child = parent * 2 + 1;}else {break;}}
}//升序建大堆 降序建小堆
void HeapSort(int* a, int n) {//建堆:从倒数第一个父节点开始向前遍历,向下调整for (int i = (n-1-1)/2; i >=0 ;i--) {AdjustDown(a,n,i);}//先将首尾元素进行交换,再向下调整while (n - 1) {swap(&a[0], &a[n - 1]);AdjustDown(a, n-1,0);n--;}
}int main() {int a[7] = { 2,6,5,1,7,4,3 };int n = sizeof(a) / sizeof(a[0]);HeapSort(a, n);for (int i = 0; i < n; i++) {printf("%d ",a[i]);}return 0;
}
🍉从时间复杂度角度分析建堆为何采取向下调整?
下面将分别分析向下调整算法建堆和向上调整算法建堆的区别:
向下调整建堆

假设节点数量为N,树的高度为h
第一层,2^0个节点,需要向下调整h-1层
第二层,2^1个节点,需要向下调整h-2层
第三层,2^2个节点,需要向下调整h-3层
……
第h层,2^h个节点,需要向下调整0层
可以看出:节点少的层向下调整得多,节点多的层向下调整得少
计算向下调整建堆最坏情况下合计的调整次数:

通过错位相减法可得:

因此向下调整建堆的时间复杂度为O(N)
向上调整建堆:

假设节点数量为N,树的高度为h
第一层,2^0个节点,需要向下调整0层
第二层,2^1个节点,需要向下调整1层
第三层,2^2个节点,需要向下调整2层
……
第h层,2^h个节点,需要向下调整h-1层
可以看出:节点少的层向上调整得少,节点多的层向上调整得多。
T(h)=2^1*1+2^2*2+……+2^(h-2)*(h-2)+2^(h-1)*(h-1)
同样由错位相减法可得:
T(h)=-(2^2+2^3+……+2^(h-1))+2^h*(h-1)-2^1
整理可得:
T(N)=-N+(N+1)*(log2(N+1)-1)+1
因此向上调整建堆的时间复杂度为O(N*logN)
所以我们选择向下建堆算法明显效率更高。
相关文章:
数据结构 | 详解二叉树——堆与堆排序
🥝堆 堆总是一棵完全二叉树。 大堆:父节点总是大于子节点。 小堆:父节点总是小于子节点。 注意:1.同一个节点下的两个子节点并无要求先后顺序。 2.堆可以是无序的。 🍉堆的实现 🌴深度剖析 1.父节点和子…...
vb.net,C#强制结束进程,“优雅”的退出方式
在VB.NET中,Application.Exit()和Environment.Exit(0)都用于结束程序,但它们的使用场景和背后的逻辑略有不同。 **Application.Exit()**: Application.Exit()通常用于Windows Forms应用程序中。当调用Application.Exit()时,它会触…...
牛客热题:数据流中的中位数
📟作者主页:慢热的陕西人 🌴专栏链接:力扣刷题日记 📣欢迎各位大佬👍点赞🔥关注🚓收藏,🍉留言 文章目录 牛客热题:数据流中的中位数题目链接方法一…...
JavaScript-JavaWeb
目录 什么是JavaScript? js引入方式 js基础语法 书写语法 变量 数据据类型 运算符 类型转换 流程语句 js函数 js对象 1.Array 2.String 3.JSON js事件监听 什么是JavaScript? ● JavaScript(简称:JS)是一门跨平台、面向对象的脚本语言。是用来控制网页行为的,它能…...
vue组件通讯$parent和$children获取单签组件的⽗组件和当前组件的⼦组件的例子
在 Vue 中,$parent 和 $children 是实例属性,允许你访问组件的父组件和子组件。但是,请注意,这些属性主要用于在开发过程中进行调试和临时访问,并不推荐在正常的组件通信中使用,因为它们破坏了组件的封装性…...
Util和utils
Util FieldStats 这段代码定义了一个名为FieldStats的Java类,位于com.cqupt.software_1.Util包中。它使用了lombok库的Data和AllArgsConstructor注解,这些注解帮助生成了getter、setter、toString等方法,以及包含所有参数的构造函数。类中有…...
拷贝构造、移动构造、拷贝赋值、移动赋值
最近在学习C的拷贝构造函数时发现一个问题:在函数中返回局部的类对象时,并没有调用拷贝构造函数。针对这个问题,查阅了一些资料,这里记录整理一下。 调用拷贝构造函数的三种情况: ① 用一个类去初始化另一个对象时&a…...
Python3 笔记:math模块
要使用 math 函数必须先导入math模块 语法:import math Python math 模块提供了许多对浮点数的数学运算函数。 math 模块下的函数,返回值均为浮点数,除非另有明确说明。 如果需要计算复数,需使用 cmath 模块中的同名函数。 m…...
python -【四】函数
函数 一、函数的基础 函数:是组织好的,可以重复使用的,用来实现特定功能的代码段 语法 def 函数名(入参): return 出参 # 定义函数 def out_hello():print(hello ~~~)# 调用/使用/执行函数 out_hello()练习题 自定义一个函数,…...
力扣 5. 最长回文子串 python AC
动态规划 class Solution:def longestPalindrome(self, s):size len(s)maxl 1start 0dp [[False] * size for _ in range(size)]for i in range(size):dp[i][i] Truefor L in range(2, size 1):for i in range(size):j L i - 1if j > size:breakif s[i] s[j]:if L…...
【微机原理及接口技术】可编程计数器/定时器8253
【微机原理及接口技术】可编程计数器/定时器8253 文章目录 【微机原理及接口技术】可编程计数器/定时器8253前言一、8253的内部结构和引脚二、8253的工作方式三、8253的编程总结 前言 本篇文章就8253芯片展开,详细介绍8253的内部结构和引脚,8253的工作方…...
23种设计模式之一— — — —装饰模式详细介绍与讲解
装饰模式详细讲解 一、定义二、装饰模式结构核心思想模式角色模式的UML类图应用场景模式优点模式缺点 实例演示图示代码演示运行结果 一、定义 装饰模式(别名:包装器) 装饰模式(Decorator Pattern)是结构型的设计模式…...
2024年2月28日 星期三
2024年2月28日 星期三 农历正月十九 1. 住建部:各城市要做好今明两年住房发展计划,防止市场大起大落。 2. 政协委员赵长龙建议:增加元旦、端午、中秋高速免费,周六日半价。 3. 人民法院案例库开始对社会开放,与中国…...
Java中的super关键字详解
在Java编程中,super关键字是一个非常重要的概念,尤其是在继承和多态的场景中。理解super关键字的使用方法和其背后的机制,对于掌握面向对象编程(OOP)的基本概念至关重要。本篇博客将详细讲解super关键字的各种用法及其…...
消消乐游戏开发,三消游戏,消除小游戏
消消乐是一款非常受欢迎的休闲消除类游戏,通常也被称为“三消游戏”。这类游戏的主要目标是通过交换和匹配三个或更多相同的物品来清除它们,从而得分并通过关卡。以下是一些消消乐游戏的基本特点和玩法: 基本玩法 交换和匹配:玩…...
三十三、openlayers官网示例Drawing Features Style——在地图上绘制图形,并修改绘制过程中的颜色
这篇讲的是使用Draw绘制图形时根据绘制形状设置不同颜色。 根据下拉框中的值在styles对象中取对应的颜色对象,new Draw的时候将其设置为style参数。 const styles {Point: {"circle-radius": 5,"circle-fill-color": "red",},LineS…...
Vue——事件修饰符
文章目录 前言阻止默认事件 prevent阻止事件冒泡 stop 前言 在官方文档中对于事件修饰符有一个很好的说明,本篇文章主要记录验证测试的案例。 官方文档 事件修饰符 阻止默认事件 prevent 在js原生的语言中,可以根据标签本身的事件对象进行阻止默认事件…...
Go语言GoFly框架快速新增接口/上手写代码
拿到一个新框架大家可能无从下手,因为你对框架设计思路、结构不了解,从而产生恐惧,所以我们框架是通过简单可视化界面安装,安装后即可看到效果,然后点击先点点看各个功能,看现有的功能是怎么写的࿰…...
【Vue】v-else 和 v-else-if
作用:辅助v-if进行判断渲染 语法: v-else v-else-if"表达式"PS:需要紧接着v-if使用 示例代码: <body><div id"app"><p v-if"gender 1">性别:♂ 男</p><…...
一致性hash算法原理图和负载均衡原理-urlhash与least_conn案例
一. 一致性hash算法原理图 4台服务器计算hash值图解 减少一台服务3台服务器计算hash值图解 增加一台服务器5台服务器计算hash值图解 二. 负载均衡原理-urlhash与least_conn 2.1.urlhash案例 # urlhash upstream tomcats {hash $requ...
Vue2 第一节_Vue2上手_插值表达式{{}}_访问数据和修改数据_Vue开发者工具
文章目录 1.Vue2上手-如何创建一个Vue实例,进行初始化渲染2. 插值表达式{{}}3. 访问数据和修改数据4. vue响应式5. Vue开发者工具--方便调试 1.Vue2上手-如何创建一个Vue实例,进行初始化渲染 准备容器引包创建Vue实例 new Vue()指定配置项 ->渲染数据 准备一个容器,例如: …...
Frozen-Flask :将 Flask 应用“冻结”为静态文件
Frozen-Flask 是一个用于将 Flask 应用“冻结”为静态文件的 Python 扩展。它的核心用途是:将一个 Flask Web 应用生成成纯静态 HTML 文件,从而可以部署到静态网站托管服务上,如 GitHub Pages、Netlify 或任何支持静态文件的网站服务器。 &am…...
linux 下常用变更-8
1、删除普通用户 查询用户初始UID和GIDls -l /home/ ###家目录中查看UID cat /etc/group ###此文件查看GID删除用户1.编辑文件 /etc/passwd 找到对应的行,YW343:x:0:0::/home/YW343:/bin/bash 2.将标红的位置修改为用户对应初始UID和GID: YW3…...
解决本地部署 SmolVLM2 大语言模型运行 flash-attn 报错
出现的问题 安装 flash-attn 会一直卡在 build 那一步或者运行报错 解决办法 是因为你安装的 flash-attn 版本没有对应上,所以报错,到 https://github.com/Dao-AILab/flash-attention/releases 下载对应版本,cu、torch、cp 的版本一定要对…...
MySQL 部分重点知识篇
一、数据库对象 1. 主键 定义 :主键是用于唯一标识表中每一行记录的字段或字段组合。它具有唯一性和非空性特点。 作用 :确保数据的完整性,便于数据的查询和管理。 示例 :在学生信息表中,学号可以作为主键ÿ…...
认识CMake并使用CMake构建自己的第一个项目
1.CMake的作用和优势 跨平台支持:CMake支持多种操作系统和编译器,使用同一份构建配置可以在不同的环境中使用 简化配置:通过CMakeLists.txt文件,用户可以定义项目结构、依赖项、编译选项等,无需手动编写复杂的构建脚本…...
Python常用模块:time、os、shutil与flask初探
一、Flask初探 & PyCharm终端配置 目的: 快速搭建小型Web服务器以提供数据。 工具: 第三方Web框架 Flask (需 pip install flask 安装)。 安装 Flask: 建议: 使用 PyCharm 内置的 Terminal (模拟命令行) 进行安装,避免频繁切换。 PyCharm Terminal 配置建议: 打开 Py…...
基于开源AI智能名片链动2 + 1模式S2B2C商城小程序的沉浸式体验营销研究
摘要:在消费市场竞争日益激烈的当下,传统体验营销方式存在诸多局限。本文聚焦开源AI智能名片链动2 1模式S2B2C商城小程序,探讨其在沉浸式体验营销中的应用。通过对比传统品鉴、工厂参观等初级体验方式,分析沉浸式体验的优势与价值…...
Python爬虫实战:研究Restkit库相关技术
1. 引言 1.1 研究背景与意义 在当今信息爆炸的时代,互联网上存在着海量的有价值数据。如何高效地采集这些数据并将其应用于实际业务中,成为了许多企业和开发者关注的焦点。网络爬虫技术作为一种自动化的数据采集工具,可以帮助我们从网页中提取所需的信息。而 RESTful API …...
渗透实战PortSwigger Labs指南:自定义标签XSS和SVG XSS利用
阻止除自定义标签之外的所有标签 先输入一些标签测试,说是全部标签都被禁了 除了自定义的 自定义<my-tag onmouseoveralert(xss)> <my-tag idx onfocusalert(document.cookie) tabindex1> onfocus 当元素获得焦点时(如通过点击或键盘导航&…...

