数据结构 | 详解二叉树——堆与堆排序

news/2024/7/22 0:48:40/文章来源:https://blog.csdn.net/mooridy/article/details/139032799

🥝堆

堆总是一棵完全二叉树。

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

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

注意:1.同一个节点下的两个子节点并无要求先后顺序。

           2.堆可以是无序的。

🍉堆的实现

🌴深度剖析

1.父节点和子节点之间的关系

子节点=(父节点*2)+1

或者子节点=(父节点*2)+2

父节点=(子节点-1)/2

2.堆的插入HeapPush实现

先插入一个10到数组的尾上,再进行向上调整算法,直到满足堆
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)

所以我们选择向下建堆算法明显效率更高。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.ldbm.cn/p/430564.html

如若内容造成侵权/违法违规/事实不符,请联系编程新知网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

LLAMA3==shenzhi-wang/Llama3-8B-Chinese-Chat。windows安装不使用ollama

创建环境&#xff1a; conda create -n llama3_env python3.10 conda activate llama3_env conda install pytorch torchvision torchaudio cudatoolkit11.7 -c pytorch 安装Hugging Face的Transformers库&#xff1a; pip install transformers sentencepiece 下载模型 ht…

服务器内存与CPU要占用多少才合理?

一 通常服务器内存占用多少合理&#xff1f;cpu占用多少才合理&#xff1f; 1 通常配置范围建议&#xff1a; 建议CPU使用率不高于80%&#xff1b;内存使用率不高于80%&#xff1b; 注意&#xff1a;具体情况还需要根据服务器的实际负载和应用场景来判断。 2 内存使用率&…

组件的传参等

一:组件的生命周期函数 组件的生命周期函数: created只是创建了组件内的实例对象 attached,给组件实例绑定了属性,绑定到页面节点树之后 ready准备好渲染之后,还未渲染之前 moved组件实例被移动到另一个位置后执行 detached在整个组件被被移除执行 error执行的时候,组件内…

景源畅信电商:抖音开店步骤是什么?

随着社交媒体的兴起&#xff0c;抖音已经成为一个不可忽视的电商平台。许多人都希望通过抖音开店来实现自己的创业梦想。那么&#xff0c;抖音开店的具体步骤是什么呢?接下来&#xff0c;我们将详细阐述这一问题。 一、明确回答问题抖音开店的步骤主要包括&#xff1a;注册账号…

Java基础20(文件操作 IO流 InputStream字节输入流 OutputStream字节输出流 Writer 字符输出流)

目录 一、File 文件对象 1. 创建对象 2. 相对路径和绝对路径 3. 一些方法 汇总&#xff1a; 获取文件信息1&#xff1a; 判断文件&#xff1a; 删除文件&#xff1a; 创建文件&#xff1a; 获取文件信息2&#xff1a; 4. 小结 二、IO流 1. InputStream字节输入流 …

LPDDR6带宽预计将翻倍增长:应对低功耗挑战与AI时代能源需求激增

在当前科技发展的背景下&#xff0c;低能耗问题成为了业界关注的焦点。国际能源署(IEA)近期报告显示&#xff0c;日常的数字活动对电力消耗产生显著影响——每次Google搜索平均消耗0.3瓦时&#xff08;Wh&#xff09;&#xff0c;而向OpenAI的ChatGPT提出的每一次请求则消耗2.9…

利用C++与Python调用千帆免费大模型,构建个性化AI对话系统

千帆大模型已于2024年4月25日正式免费&#xff0c;调用这个免费的模型以实现自己的AI对话功能&#xff0c;遵循以下步骤&#xff1a; 了解千帆大模型&#xff1a; 千帆大模型是百度智能云推出的一个平台&#xff0c;提供了一系列AI能力和工具&#xff0c;用于快速开发和应用A…

【busybox记录】【shell指令】rmdir

目录 内容来源&#xff1a; 【GUN】【rmdir】指令介绍 【busybox】【rmdir】指令介绍 【linux】【rmdir】指令介绍 使用示例&#xff1a; 删除空目录 - 默认 删除dirname下的所有空目录&#xff0c;包括因删除其他目录而变为空的目录 常用组合指令&#xff1a; 指令不…

在做题中学习(62):矩阵区域和

1314. 矩阵区域和 - 力扣&#xff08;LeetCode&#xff09; 解法&#xff1a;二维前缀和 思路&#xff1a;读题画图才能理解意思&#xff1a;dun点点的是mat中的一个数&#xff0c;而要求的answer同位置的数 以点为中心上下左右延长 k 个单位所围成长方形的和。 因为最后answ…

前端学习--React部分

文章目录 前端学习--React部分前言1.React简介1.1React的特点1.2引入文件1.3JSX&#x1f349;JSX简介与使用&#x1f349;JSX语法规则 1.4模块与组件&#x1f349;模块&#x1f349;组件 1.5安装开发者工具 2.React面向组件编程2.1创建组件&#x1f349;函数式组件&#x1f349…

【数据结构:排序算法】堆排序(图文详解)

&#x1f381;个人主页&#xff1a;我们的五年 &#x1f50d;系列专栏&#xff1a;数据结构课程学习 &#x1f389;欢迎大家点赞&#x1f44d;评论&#x1f4dd;收藏⭐文章 目录 &#x1f369;1.大堆和小堆 &#x1f369;2.向上调整算法建堆和向下调整算法建堆&#xff1a;…

内存函数<C语言>

前言 前面两篇文章介绍了字符串函数&#xff0c;不过它们都只能用来处理字符串&#xff0c;C语言中也内置了一些内存函数来对不同类型的数据进行处理&#xff0c;本文将介绍&#xff1a;memcpy()使用以及模拟实现&#xff0c;memmove()使用以及模拟实现&#xff0c;memset()使用…

【C++】模拟实现string类

&#x1f984;个人主页:修修修也 &#x1f38f;所属专栏:C ⚙️操作环境:Visual Studio 2022 目录 一.了解项目功能 二.逐步实现项目功能模块及其逻辑详解 &#x1f38f;构建成员变量 &#x1f38f;实现string类默认成员函数 &#x1f4cc;构造函数 &#x1f4cc;析构函数…

python从0开始学习(十二)

目录 前言 1、字符串的常用操作 2、字符串的格式化 2.1 格式化字符串的详细格式&#xff08;针对format形式&#xff09; ​编辑 总结 前言 上一篇文章我们讲解了两道关于组合数据类型的题目&#xff0c;本篇文章我们将学习新的章节&#xff0c;学习字符串及正则表达式。 …

SAP 生产订单报工函数BAPI_PRODORDCONF_CREATE_TT不返回报错信息

最近财务一直反馈MES报工的数据都没有成本,然后去查看原因发现是财务当月的KP26的价格没有进行维护,导致没有收集到工单的报工成本。 但是在前台操作CO11 报工的时候,系统会给出报错的信息 但是我们在调用函数BAPI_PRODORDCONF_CREATE_TT的时候,系统并没有返回报错的信息…

【SPSS】基于因子分析法对水果茶调查问卷进行分析

&#x1f935;‍♂️ 个人主页&#xff1a;艾派森的个人主页 ✍&#x1f3fb;作者简介&#xff1a;Python学习者 &#x1f40b; 希望大家多多支持&#xff0c;我们一起进步&#xff01;&#x1f604; 如果文章对你有帮助的话&#xff0c; 欢迎评论 &#x1f4ac;点赞&#x1f4…

数据库之Mysql提权

MySQL UDF 提权 UDF&#xff08;user defined function&#xff09;⽤户⾃定义函数&#xff0c;是 mysql 的⼀个拓展接⼝。⽤户可以通过⾃定义函数实现在mysql中⽆法⽅便实现的功能&#xff0c;其添加的新函数都可以在 sql 语句中调⽤&#xff0c;就像调⽤本机函数⼀样。 先前…

使用Word表格数据快速创建图表

实例需求&#xff1a;Word的表格如下所示&#xff0c;标题行有合并单元格。 现在需要根据上述表格数据&#xff0c;在Word中创建如下柱图。如果数据在Excel之中&#xff0c;那么创建这个图并不复杂&#xff0c;但是Word中就没用那么简单了&#xff0c;虽然Word中可以插入图表&a…

Sourcetree安装教程及使用

1 Sourcetree介绍 Sourcetree是一款免费的Git图形化客户端&#xff0c;它由Atlassian开发&#xff0c;提供了跨平台的支持&#xff0c;可运行在Windows和Mac操作系统上。Sourcetree可以让开发者更方便地使用Git来管理代码&#xff0c;不需要在命令行中输入复杂的Git命令&#x…

Paddle使用问题No module named ‘paddle.fluid’

这是Paddle版本的问题&#xff0c;从飞桨框架 2.5 版本开始&#xff0c;已经废弃了 paddle.fluid 。 ​解决方案&#xff1a;修改paddle版本 pip install paddlepaddle2.4.0