数据结构——二叉树之c语言实现堆与堆排序

目录

前言：

1.二叉树的概念及结构

1.1 特殊的二叉树 

1.2 二叉树的存储结构

   1.顺序存储

2.链式存储 

2. 二叉树的顺序结构及实现 

2.1 堆的概念 

  ​编辑

2.2 堆的创建

3.堆的实现

3.1 堆的初始化和销毁 

初始化：

销毁： 

插入：

向上调整：

删除： 

向下调整： 

堆顶元素： 

判空： 

 4.堆排序

4.1排序实现

 

前言：

   在上一期我们介绍了有关于树的基础概念，了解了关于树的各名称的含义，然而在现实中树被用得最多的场景还是在我们计算机中的资源管理器的文件存储结构中，在其他场景被使用的情况很少，所以我们这一期要介绍一种被广泛使用的树型结构——二叉树。

1.二叉树的概念及结构

  顾名思义，二叉树是由一个根结点和两棵子树构成，二叉树的每个结点最多只有两个结点：

从上图可以看出：

1. 二叉树不存在度大于2的结点

2. 二叉树的子树有左右之分，次序不能颠倒，因此二叉树是有序树  

二叉树是由以下几种情况复合而成的：

 

现实中的二叉树：

1.1 特殊的二叉树 

 1. 满二叉树：一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是说，如果一个二叉树的层数为K，且结点总数K次方-1，则它就是满二叉树。

2. 完全二叉树：完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K 的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树。

1.2 二叉树的存储结构

  二叉树一般可以使用两种结构存储，一种顺序结构，一种链式结构。

   1.顺序存储

  顺序结构存储就是使用数组来存储，一般使用数组只适合表示完全二叉树，因为不是完全二叉树会有空间的浪费。而现实中使用中只有堆才会使用数组来存储，关于堆我们后面的章节会专门讲解。二叉树顺 序存储在物理上是一个数组，在逻辑上是一颗二叉树。 

2.链式存储 

    二叉树的链式存储结构是指，用链表来表示一棵二叉树，即用链来指示元素的逻辑关系。 通常的方法是 链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别用来给出该结点左孩子和右孩子所 在的链结点的存储地址 。链式结构又分为二叉链和三叉链，当前我们学习中一般都是二叉链，后面课程 学到高阶数据结构如红黑树等会用到三叉链。

 

2. 二叉树的顺序结构及实现 

  普通的二叉树是不适合用数组来存储的，因为可能会存在大量的空间浪费。而完全二叉树更适合使用顺序结 构存储。现实中我们通常把堆(一种二叉树)使用顺序结构的数组来存储，需要注意的是这里的堆和操作系统虚拟进程地址空间中的堆是两回事，一个是数据结构，一个是操作系统中管理内存的一块区域分段。

2.1 堆的概念 

  

堆的性质：

1.堆中某个结点的值总是不大于或不小于其父结点的值。

2.堆总是一棵完全二叉树。 

 

2.2 堆的创建

  下面我们给出一个数组，这个数组逻辑上可以看做一颗完全二叉树，但是还不是一个堆，现在我们通过算 法，把它构建成一个堆。根结点左右子树不是堆，我们怎么调整呢？这里我们从倒数的第一个非叶子结点的子树开始调整，一直调整到根结点的树，就可以调整成堆。

3.堆的实现

 介绍完堆的概念和性质之后，我们接下来就要来用代码实现堆及堆的各个方法。由于堆是顺序结构实现的，所以我们选择使用顺序表来实现它：

typedef int HPDataType;
typedef struct Heap
{HPDataType* a;int size;int capacity;
}HP;

3.1 堆的初始化和销毁 

  堆是用顺序表来实现的，而顺序表的空间都是我们手动在内存中的堆中开辟的，所以也需要手动释放，而在程序最初运行时我们也要对它进行初始化。

初始化：

void HPInit(HP* php)
{assert(php);php->a = NULL;php->size = php->capacity = 0;
}//初始化

销毁： 

void HPDestroy(HP* php)
{assert(php);free(php->a);php->a = NULL;php->capacity = php->size = 0;
}//销毁

插入：

 在插入数据之前，我们选确定空间够不够，如果city等于cpapcity，我们就判断空间满了，需要扩容，然后插入数据，而要实现建堆的话，我们还需要使用向上调整方法实现：

void HPPush(HP* php, HPDataType x)
{assert(php);if (php->capacity == php->size){int newcapacity = php->capacity == 0 ? 4 : php->capacity * 2;HPDataType* tmp = (HPDataType*)realloc(php->a, sizeof(HPDataType) * newcapacity);if (tmp == NULL){perror("realloc fail!");}php->a = tmp;php->capacity = newcapacity;}php->a[php->size] = x;php->size++;AdjustUp(php->a, php->size-1);//向上调整
}//插入

向上调整：

   向上调整是建堆的关键，在我们插入一个数据时，我们之前建的堆可能会遭到破坏，这时就需要重新调整建堆，我们插入操作是尾插，用堆来表示的话它就是在堆低，这时我们就要向上调整，如果我们建的是小堆，那么我们就要判断我们插入的结点与它的父结点的大小关系，如果它比它的父结点小的话。那么就要与它的父结点交换位置，走到下一轮，如果它还是小于自己的父节点，那么继续执行交换操作，直到数组变成一个小堆：

代码实现：

void AdjustUp(HPDataType* a,  int child)
{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;}}
}

删除： 

  有插入操作就必然有删除操作，那么我们如何实现删除操作呢？如果我们直接进行头删，那么我们建的堆就会被破环，如果尾删的话，那么堆就没有意义了（后面详细解释），所以我们先让堆中第一个元素与最后一个元素交换，然后再让size减一，而这时我们建的堆被破环了，所以还需要使用向下调整方法来重新建堆，而向下建堆的算法也比较简单，先找出第一个结点更小的那个子结点，只要这个结点比它的父结点小就让它们交换位置，如此循环往复，直到走到堆尾：

删除代码实现：

void HPPop(HP* php)
{assert(&php);assert(php->size > 0);swap(&(php->a[0]), &(php->a[php->size - 1]));php->size--;AdjustDown(php->a,php->size,0);//向下调整
}//删除

向下调整： 

void AdjustDown(HPDataType* a, int n, int parent)
{//假设更小的孩子是左孩子int child = parent * 2 + 1;while (child<n)//child>=n说明孩子已经不存在{if (child+1<n&&a[child + 1] < a[child]){child++;}if (a[child] < a[parent]){swap(&a[child], &a[parent]);parent = child;child = parent * 2 + 1;}else{break;}}}//向下调整

堆顶元素： 

HPDataType HPTop(HP* php)
{assert(php);assert(php->size > 0);return php->a[0];
}//堆顶元素

判空： 

bool HPEmpty(HP* php)
{assert(php);return php->size = 0;
}//判空

 4.堆排序

 堆排序是一种速度很快的排序算法，冒泡排序的时间复杂度为O（N^2），而堆排序的时间复杂度仅为O（logN），学完堆，我们就可以来试着实现堆排序了。

4.1排序实现

 我们先创建一个无序数组：

int a[] = { 8,6,5,3,9,0,7,1,4,2 };

现在这个数组不是堆，我们堆排序的第一步就是先建堆呢，可以使用向下调整吗，答案是不可以，只有下面的子树都是堆时才可以使用，而现在这棵树仅是一个无序数组，所以我们选择从后往前建堆，什么意思呢，我们可以把这组树看成一棵一棵树：

 

我们发现，从9开始，往上每一个结点都有自己的子结点，这就意味着从就开始，每往前走一步就是一棵树，所以我们只要从9开始使用向下调整建堆，每往前走一步就可以实现一棵树的建堆，而走到8时，整棵树也就完成了建堆：

int a[] = { 8,6,5,3,9,0,7,1,4,2 };
int len = sizeof(a) / sizeof(int);
for (int i = (len - 1 - 1) / 2; i >= 0; i--)
{AdjustDown(a, len, i);
}//建堆

这个算法到底怎么样呢？我们运行一下程序看看：

 

我们将这些数字摆成一棵二叉树：

 

从上图可以看出，这组数字摆成一棵二叉树它就是一个标准的堆。 

     成功建堆之后，我们就可以来使用堆来排序了，从上图可以看出，我们建的是小堆，如果我们要实现降序，可以使用小堆实现吗？答案是可以，而且经过实验，我们得出结论：升序：建大堆 ，降序：建小堆，所以我们使用小堆来实现降序是没有问题的。如何实现呢，我们可以先创建一个变量end指向最后一个结点，然后让第一个结点和尾结点交换，因为第一个结点是整个堆最小的数，交换位置之后，最小的数就在最后一个结点了，我们让end向前走一步，然后使用向下调整让堆第二小的数字走到第一个结点，然后再和end指向的结点交换，循环往复之后最大的数就走到了第一个结点，而我们也完成了降序排序：

while (end > 0){swap(&a[0], &a[end]);end--;AdjustDown(a, end, 0);}//调整

来看看结果：

 

 下面是完整代码：

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
void swap(int* p1, int* p2)
{int tmp = *p1;*p1 = *p2;*p2 = tmp;
}
void AdjustDown(int* a, int n, int parent)
{int child = parent * 2 + 1;while (child<n){if (child+1<n&&a[child + 1] < a[child]){child++;}if (a[child] < a[parent]){swap(&a[child], &a[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}void test()
{int a[] = { 8,6,5,3,9,0,7,1,4,2 };int len = sizeof(a) / sizeof(int);for (int i = (len - 1 - 1) / 2; i >= 0; i--){AdjustDown(a, len, i);}//建堆int end = len - 1;while (end > 0){swap(&a[0], &a[end]);end--;AdjustDown(a, end, 0);}//调整for (int i = 0; i < len; i++){printf("%d ", a[i]);}
}
int main()
{test();return 0;
}

到这里我们的堆就结束了，我将代码放在下面，感兴趣的小伙伴可以试试哦。

Heap.h :

#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;
}HP;void HPInit(HP* php);//初始化
void HPDestroy(HP* php);//销毁
void HPPush(HP* php, HPDataType x);//插入
void HPPop(HP* php);//删除
HPDataType HPTop(HP* php);//堆顶元素
void AdjustUp(HPDataType* a, int child);//向上调整
void AdjustDown(HPDataType* a, int n,int parent);//向下调整
bool HPEmpty(HP* php);//判空

Heap.c :

#define _CRT_SECURE_NO_WARNINGS 1
#include"Heap.h"void HPInit(HP* php)
{assert(php);php->a = NULL;php->size = php->capacity = 0;
}//初始化
void swap(HPDataType* p1, HPDataType* p2)
{HPDataType tmp = *p1;*p1 = *p2;*p2 = tmp;
}//交换
void AdjustDown(HPDataType* a, int n, int parent)
{//假设更小的孩子是左孩子int child = parent * 2 + 1;while (child<n)//child>=n说明孩子已经不存在{if (child+1<n&&a[child + 1] < a[child]){child++;}if (a[child] < a[parent]){swap(&a[child], &a[parent]);parent = child;child = parent * 2 + 1;}else{break;}}}//向下调整
void AdjustUp(HPDataType* a,  int child)
{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 HPPush(HP* php, HPDataType x)
{assert(php);if (php->capacity == php->size){int newcapacity = php->capacity == 0 ? 4 : php->capacity * 2;HPDataType* tmp = (HPDataType*)realloc(php->a, sizeof(HPDataType) * newcapacity);if (tmp == NULL){perror("realloc fail!");}php->a = tmp;php->capacity = newcapacity;}php->a[php->size] = x;php->size++;AdjustUp(php->a, php->size-1);//向上调整
}//插入
void HPPop(HP* php)
{assert(&php);assert(php->size > 0);swap(&(php->a[0]), &(php->a[php->size - 1]));php->size--;AdjustDown(php->a,php->size,0);//向下调整
}//删除
HPDataType HPTop(HP* php)
{assert(php);assert(php->size > 0);return php->a[0];
}//堆顶元素
bool HPEmpty(HP* php)
{assert(php);return php->size = 0;
}//判空void HPDestroy(HP* php)
{assert(php);free(php->a);php->a = NULL;php->capacity = php->size = 0;
}//销毁

test.c :

#define _CRT_SECURE_NO_WARNINGS 1
#include"Heap.h"
void test()
{int a[] = { 4,9,0,2,5,3,7,1,8,6 };HP hp;HPInit(&hp);for (size_t i = 0; i < sizeof(a) / sizeof(int); i++){HPPush(&hp, a[i]);}while (hp.size){printf("%d ", hp.a[hp.size - 1]);hp.size--;}HPDestroy(&hp);
}
void test02()
{int a[] = { 4,9,0,2,5,3,7,1,8,6 };HP hp;HPInit(&hp);for (size_t i = 0; i < sizeof(a) / sizeof(int); i++){HPPush(&hp, a[i]);}while (hp.size>0){int top = HPTop(&hp);printf("%d ", top);HPPop(&hp);}HPDestroy(&hp);}
void test03()
{int a[] = { 4,9,0,2,5,3,7,1,8,6 };size_t len = sizeof(a) / sizeof(int);for (int i = (len - 1 - 1) / 2; i >= 0; i--){AdjustDown(a, len, i);}int end = len - 1;while (end>0){swap(&a[0], &a[end]);AdjustDown(a, end, 0);end--;}for (int i = 0; i < len; i++){printf("%d ", a[i]);}
}
int main()
{//test02();test03();return 0;
}

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

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

相关文章

【SVN的使用- SVN的基本命令-SVN命令简写-注意事项-解决冲突 Objective-C语言】

【SVN的使用- SVN的基本命令-SVN命令简写-注意事项-解决冲突 Objective-C语言】

一、SVN的更新命令：update 1.服务器如果新建了一个文件夹，yuanxing，版本变成6了， 我现在本地还只有三个文件夹，版本5， 终端里边，我们敲一个svn update， 我这儿就多了一个yuanxing文件夹， 这个就是更新，就是把服务器最新的代码下载下来， 假设服务器上大家提交了这…
阅读更多...
双向链表 -- 详细理解和实现

双向链表 -- 详细理解和实现

欢迎光顾我的homepage 前言 双向链表是一种带头双向循环的链表。在双向链表中&#xff0c;首先存在着一个头结点&#xff1b;其次每个节点有指向下一个节点的指针next 和指向上一个节点的指针prev &#xff1b…
阅读更多...
MySQL安全值守常用语句

MySQL安全值守常用语句

一、用户权限设置 1、Mysql中用户是如何定义的 用户名主机域 10.0.0.5110.0.0.%%10.0.0.0/255.255.255.0Db01Localhost127.0.0.1 2、用户创建 create user xinjing% identified by 123 3、用户删除 drop user username&#xff1b;username 是要删除的用户名:如 drop user root…
阅读更多...
Docker 基本管理及部署

Docker 基本管理及部署

目录 1.Docker概述 1.1 Docker是什么&#xff1f; 1.2 Docker的宗旨 1.3 容器的优点 1.4 Docker与虚拟机的区别 1.5 容器在内核中支持的两种技术 1.6 namespace的六大类型 2.Docker核心概念 2.1 镜像 2.2 容器 2.3 仓库 3.安装Docker 3.1 查看 docker 版本信息 4.…
阅读更多...
SpringBoot新手快速入门系列教程十：基于docker容器，部署一个简单的项目

SpringBoot新手快速入门系列教程十：基于docker容器，部署一个简单的项目

前述&#xff1a; 本篇教程将略过很多docker下载环境配置的基础步骤&#xff0c;如果您对docker不太熟悉请参考我的上一个教程&#xff1a;SpringBoot新手快速入门系列教程九&#xff1a;基于docker容器&#xff0c;部署一个简单的项目 使用 Docker Compose 支持部署 Docker 项…
阅读更多...
LLM基础模型系列：Fine-Tuning总览

LLM基础模型系列：Fine-Tuning总览

由于对大型语言模型&#xff0c;人工智能从业者经常被问到这样的问题&#xff1a;如何训练自己的数据&#xff1f;回答这个问题远非易事。生成式人工智能的最新进展是由具有许多参数的大规模模型驱动的&#xff0c;而训练这样的模型LLM需要昂贵的硬件&#xff08;即许多具有大量…
阅读更多...
51单片机(STC8051U34K64)_RA8889_SPI4参考代码（v1.3)

51单片机(STC8051U34K64)_RA8889_SPI4参考代码（v1.3)

硬件&#xff1a;STC8051U34K64 RA8889开发板&#xff08;硬件跳线变更为SPI-4模式&#xff0c;PS101&#xff0c;R143&#xff0c;R141短接&#xff0c;R142不接&#xff09; STC8051U34K64是STC最新推出来的单片机&#xff0c;主要用于替换传统的8051单片机&#xff0c;与标…
阅读更多...
达梦数据库中的线程和进程

达梦数据库中的线程和进程

达梦数据库中的线程和进程 在达梦数据库中&#xff0c;线程和进程的概念与操作系统中的定义类似&#xff0c;但有一些特定的实现细节和用途。以下是达梦数据库中线程和进程的一些关键点&#xff1a; 进程&#xff08;Process&#xff09;&#xff1a; 在达梦数据库中&#x…
阅读更多...
oracle哪些后台进程不能杀？

oracle哪些后台进程不能杀？

oracle 有很多的后台进程&#xff0c;在遇到特殊情况的时候如锁表&#xff0c;如果等待的是一个后台进程&#xff0c;那这时就需要考量是不是能杀掉这个后台进程&#xff1f;杀掉这个后台进程会不会引起实例崩溃&#xff1f;本着实践出真知&#xff0c;本文针对oracle 11g&…
阅读更多...
RK3588编译rkmpp，拉取海康威视网络摄像头264码流并运行yolo

RK3588编译rkmpp，拉取海康威视网络摄像头264码流并运行yolo

硬件&#xff1a;EVB评估版 SOC&#xff1a;Rockchip RK3588 背景&#xff1a; 由于项目需要&#xff0c;需要拉取264码流&#xff0c;并通过将yolov5s.pt将模型转化为rknn模型&#xff0c;获取模型分析结果。取流可以通过软件解码或者硬件解码&#xff0c;硬件解码速度更快&…
阅读更多...
插片式远程 I/O模块：热电阻温度采集模块与PLC配置案例

插片式远程 I/O模块：热电阻温度采集模块与PLC配置案例

XD系列成套系统主要由耦合器、各种功能I/O模块、电源辅助模块以及终端模块组成。有多种通讯协议总线的耦合器&#xff0c;例如Profinet、EtherCAT、Ethernet/IP、Cclink IE以及modbus/TCP等。I/O 模块可分为多通道数字量输入模块、数字量输出模块、模拟量输入模块、模拟量输出模…
阅读更多...
[leetcode]minimum-cost-to-reach-destination-in-time 规定时间内到达终点的最小费用

[leetcode]minimum-cost-to-reach-destination-in-time 规定时间内到达终点的最小费用

. - 力扣&#xff08;LeetCode&#xff09; class Solution { private:// 极大值static constexpr int INFTY INT_MAX / 2;public:int minCost(int maxTime, vector<vector<int>>& edges, vector<int>& passingFees) {int n passingFees.size();ve…
阅读更多...
2024年文化研究与数字媒体国际会议 (CRDM 2024)

2024年文化研究与数字媒体国际会议 (CRDM 2024)

2024年文化研究与数字媒体国际会议 (CRDM 2024) 2024 International Conference on Cultural Research and Digital Media 【重要信息】 大会地点&#xff1a;珠海 大会官网&#xff1a;http://www.iccrdm.com 投稿邮箱&#xff1a;iccrdmsub-conf.com 【注意&#xff1a;稿将…
阅读更多...
STL（一）

STL（一）

书写形式&#xff1a;string (const string& str, size_t pos, size_t len npos); 举例&#xff1a; int main(){ string url("https://mp.csdn.net/mp_blog/creation/editor?spm1000.2115.3001.4503") string sub1(url,0,5);//从下标为0开始向后5个字符&…
阅读更多...
Hvv工具推荐——IWannaGetAll

Hvv工具推荐——IWannaGetAll

OA基本上是每次hvv中都会被突破的&#xff0c;基本上也都会爆出各种各样的0day&#xff0c;如果真的0day防不住&#xff0c;那我们必须要把1day、nday做一遍检查。 IWannaGetAll 是一款专门针对主流OA&#xff08;办公自动化&#xff09;系统的漏洞检测和利用工具。 IWannaGe…
阅读更多...
【正点原子K210连载】第二十一章 machine.UART类实验摘自【正点原子】DNK210使用指南-CanMV版指南

【正点原子K210连载】第二十一章 machine.UART类实验摘自【正点原子】DNK210使用指南-CanMV版指南

1&#xff09;实验平台&#xff1a;正点原子ATK-DNK210开发板 2&#xff09;平台购买地址https://detail.tmall.com/item.htm?id731866264428 3&#xff09;全套实验源码手册视频下载地址&#xff1a; http://www.openedv.com/docs/boards/xiaoxitongban 第二十一章 machine.…
阅读更多...
05：定时器中断

05：定时器中断

中断 1、定时器T0中断2、案例&#xff1a;通过定时器T0中断来实现灯间隔1s亮灭 1、当中央处理机CPU正在处理某件事的时候外界发生了紧急事件请求&#xff0c;要求CPU暂停当前的工作&#xff0c;转而去处理这个紧急事件&#xff0c;处理完以后&#xff0c;再回到原来被中断的地方…
阅读更多...
Android 使用 Debug.startMethodTracing 分析方法耗时

Android 使用 Debug.startMethodTracing 分析方法耗时

参考 Generate Trace Logs by Instrumenting Your App 官网提供了 trace 工具来分析方法耗时。 生成 trace 文件 package com.test.luodemo.trace;import androidx.appcompat.app.AppCompatActivity;import android.os.Bundle; import android.os.Debug; import android.uti…
阅读更多...
Elasticsearch：Node.js ECS 日志记录 - Winston

Elasticsearch：Node.js ECS 日志记录 - Winston

这是继上一篇文章 “Elasticsearch&#xff1a;Node.js ECS 日志记录 - Pino” 的续篇。我们继续上一篇文章来讲述使用 Winston 包来针对 Node.js 应用生成 ECS 向匹配的日子。此 Node.js 软件包为 winston 记录器提供了格式化程序&#xff0c;与 Elastic Common Schema (ECS) …
阅读更多...
axios使用sm2加密数据后请求参数多了双引号解决方法

axios使用sm2加密数据后请求参数多了双引号解决方法

axios使用sm2加密数据后请求参数多了双引号解决 背景问题描述解决过程 背景 因项目安全要求&#xff0c;需对传给后端的入参加密&#xff0c;将请求参数加密后再传给后端 前期将axios降低到1.6.7后解决了问题&#xff0c;但最近axios有漏洞&#xff0c;安全要求对版本升级&…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023