作者：几冬雪来
时间：
内容：二叉树与堆内容讲解
目录
前言：
1.完全二叉树的存储：
2.堆的实现：
1.创建文件：
2.定义结构体：
3.初始化结构体：
4.扩容空间与扩容后插入数据：
5.交换结点：
6.删除数据及调整：
7.返回根的值：
8.判断是否为空：
9.返回个数：
10.实践：
3.堆排序：
4.代码：
结尾：
前言：
在上一篇博客中，我们介绍了数据结构中的树以及二叉树它们的基本内容，而其中的二叉树经常被我们所日常使用到，那么今天我们就借用二叉树来实现我们数据结构中的一大重要知识点——堆。
1.完全二叉树的存储：
在完全二叉树的中我们一般使用顺序存储的存储方式。
在这个图表中，上面的结构是逻辑结构，下面的结构是物理结构。而且我们平时的存储结构一般都是物理结构。这里我们也可以将它的物理结构转变为我们二叉树的形式。
而且在树的板块中我们有提到要存储树或者二叉树，我们会用到——“左孩子右兄弟”的方法。这个方法在二叉树中也同样适用。那么在这里我们怎么确定我们的父与子的位置呢？
通过上表我们可以得出几道公式。
这里的公式表达的是二叉树的值在数组位置中的下标关系。而这个公式用在数组存储只适用于满二叉树和完全二叉树。如果用于非满二叉树或者完全二叉树中，这就会造成浪费空间的行为。（left/rightchild为空）
而要想要数组存储的话，我们需要对其限制条件。但是在加上限制条件之后这里就有发生了改变。
加上限制条件后，这里我们就被分成了大堆（大根堆）和小堆（小根堆）。在小根堆中，所以的父结点的值都小于或者等于子结点，如果是大根堆则反之。
而这里的这种堆的作用我们就可以用到平时的排序中去。
而在堆中，我们需要的时候会插入数据，在擦入数据的时候就还有两种情况。
如图如果在这里我们插入的值比我们的父结点要小的话，这里直接插入即可。但是要是这里插入的数据要大于父结点，那么我们就需要对其进行调整。（向上调整最多logN次）
2.堆的实现：
那么在上面讲解了种种实现堆的代码可能遇到的问题之后，写下来我们就要正式书写我们的代码了。
1.创建文件：
想要实现我们的文件第一步就是创建文件。
同样的创建头文件和源文件。
2.定义结构体：
因为在这里我们书写的话需要定义多个数据，所以我们需要创建一个结构体来保存它们。
这里的结构体的定义类似我们数组的定义，这里就不多过讲解。
3.初始化结构体：
要想使用结构体，我们就要先将其初始化。
开幕断言，接下来就是为我们的结构体中的a申请空间，同时也要在这里判断申请失败的情况。而后因为a中没有数据，我们初始化为0，现阶段最大的个数为4个，所以capacity初始化为4。
4.扩容空间与扩容后插入数据：
因为我们要不断的插入空间，空间不够的话就只能进行扩容操作。
这里插入空间还是老样子，开始判断如果size与capacity相等，说明内存已经满了。接下来就是我们的扩容操作和判断是否扩容成功。扩容成功我们将新创立的指针交给a保护，capacity乘等于2。
成功扩容之后，我们就在下标size的地方插入我们的值，然后size往下走，这里最后一行代码是交换。
5.交换结点：
如果子结点大于我们的父结点，这里就需要对数据进行调整。
这里我们就来交换数据，这里通过child来找到我们它父结点的下标值。因为我们的子结点不可能为0，所以这里我们拿来作为循环条件。如果子结点大于父结点，我们就创建一个函数将二者交换，然后再将parent变为子结点，child继续找下一个父结点，直到根结点或者中间哪个父结点大于子结点就停下后进行break。
6.删除数据及调整：
有插入数据的操作，那必然也会有删除数据的操作，但是在二叉树中我们不能随意的删除数据。
删除根结点的数据我们应该怎么做？这里我们不能使用挪动数据的方法来解决这个问题。因为我们这里一开始就是一个堆，在删除数据之后一个保持它还是一个堆。
如果挪动数据之后，它就已经不是堆了。挪动数据删除会导致我们的效率低下，父结点与子结点的关系乱套。
那我们这里有一个怎么去进行删除呢？在这里我们运用到了一种方法：让我们的根结点和最后一片叶子互换位置，这样并不会破坏堆的结构，然后将最后一片叶子删除，最后来调整我们的堆。
这里向下调整的话，我们需要拿父结点和更大一点的子结点进行比较。这样才能保证新的父结点大于我们两个子结点。（向下调整最多调整logN次）
那这里我们的代码要怎么去写它呢？
在这里，还是先断言。接下来用我们的函数来交换最后一片叶子和根结点的值，然后size–将我们最后一片叶子删除。接下来就是我们调整数据使它再变成一个堆。
这里我们可以先通过父结点来找到我们的左边的子结点。接下来就是循环，当child小于我们的个数n的时候，进入循环。因为一个根有两个子结点，因此我们也要判断两个子结点之间的大小，一开始我们就设定左结点大于右结点，如果根的左结点+1不为小于n（有右结点）且右结点大于左结点，我们就将child++，让它从指向左结点变为指向右结点。如果较大的子结点大于父结点，我们就将两个值交换，然后新的子结点设计为我们的新的根，继续求它的左结点。要是父结点大于子结点，我们就直接跳出循环。
7.返回根的值：
那么在这个代码中如果我们要返回根结点的值要怎么做？
这里断言后直接返回就行了。
8.判断是否为空：
在删除数据的时候，如果个数为0的话，接下来我们就不用再进行删除操作了。那么这里要怎么判断呢？
同时我们删除数据的代码也可以进一步完善。
9.返回个数：
在这里返回个数的操作和我们返回根结点的操作一样。
这里就直接写出来了。
10.实践：
到这里我们的代码操作都写完了，下来我们就来实践操作一下看看结果是什么？
从结果来看，它十分符合我们的预想。我们也可以对代码进行修改让它只打印我们前几个想要的数据。
3.堆排序：
接下来我们就来讲解一下堆的排序，这里有人就要问了：上面我们的这种代码不是堆排序吗？它不是堆排序，这只是一种类似堆排序的数组排序罢了。
假设我们这里给一个数组，我们要将它进行堆排序的话要怎么做？最简单粗暴的方法就是直接再写一个堆出来，但是它是下下策。因此这里我们要建堆，直接建堆一个出来。
这里我们直接建堆的话，要在已经有向上和向下调整代码的前提下。
我们来对它进行调试，第一眼看着没有什么顺序可言，但是只要我们将图画出来就可以简单明了的看出来。 
这里我们就成功的进行了堆排序的建堆操作。
在树的板块我们有讲到，我们的排序分为大堆结构和小堆结构，如果在此我们要进行排升序操作，在这里我们是建大堆还是建小堆。上面这种方法是建大堆，那么如果要建小堆的话，代码要怎么修改？
在这里就只用将大于号换为小于号即可。换完之后我们来打印看看小堆是怎么样的一个情况。
这里可以看出我们的小堆排序成功实现了。但是实际上在我们写代码的时候，在进行排升序操作时，建小堆会出现一些问题。 如果我们采取建小堆，当我们选完了最小的数之后，接下来要选出次小的数，这里会出现什么问题？
当我们小堆选完了最小的数之后，我们将它移出后要选次小的数。但是在选次小的数之前，我们一个保存剩余的代码函数一个堆，虽然这里还是一个堆，但是它的关系已经乱掉了。在原堆中，我们的1和2是兄弟关系，当原根移出之后我们需要一个新的根，这里就将2个移动上去，但是这里就会变成1和2原本的兄弟关系变成了父子关系。
如果要解决这个问题的话，我们只能重新开始建一个堆，而大堆就没有这个烦恼。
因此在这里我们也得出一个结论：
在堆这里如果我们想排升序建大堆，排降序建小堆。
4.代码：
还是老规矩我们将我们的代码写出来。（包含堆的实现和堆排序的试验）
Heap.h文件
#pragma once
#define _CRT_SECURE_NO_WARNINGS 1#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
#include <assert.h>typedef int HPDataType;typedef struct Heap
{HPDataType* a;int size;int capacity;
}HP;void HeapInit(HP* php);
void HeapPush(HP* php, HPDataType x);
void HeapPop(HP* php);
HPDataType HeapTop(HP* php);
bool HeapEmpty(HP* php);
int HeapSize(HP* php);
void AdjustUp(HPDataType* a, int child);Heap.c文件
#include "Heap.h"void HeapInit(HP* php)
{assert(php);php->a = (HPDataType*)malloc(sizeof(HPDataType) * 4);if (php->a == NULL){perror("malloc fail");return;}php->size = 0;php->capacity = 4;
}void Swap(HPDataType* p1, HPDataType* p2)
{HPDataType* x = *p1;*p1 = *p2;*p2 = x;
}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 HeapPush(HP* php, HPDataType x)
{assert(php);if (php->size == php->capacity){HPDataType* tmp = (HPDataType*)realloc(php->a,sizeof(HPDataType) * php->capacity * 2);if (tmp == NULL){perror("realloc fail");return;}php->a = tmp;php->capacity *= 2; }php->a[php->size] = x;php->size++;AdjustUp(php->a,php->size - 1);
}//前提左右子树都是大堆或者小堆
void AdjustDown(HPDataType* 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 HeapPop(HP* php)
{assert(php);assert(!HeapEmpty(php));//删除数据Swap(&php->a[0], &php->a[php->size - 1]);php->size--;AdjustDown(php->a, php->size, 0);
}HPDataType HeapTop(HP* php)
{assert(php);return php->a[0];
}bool HeapEmpty(HP* php)
{assert(php);return php->size == 0;
}int HeapSize(HP* php)
{assert(php);return php->size;
}
test.c文件
#include "Heap.h"//int main()
//{
// HP hp;
// HeapInit(&hp);
// HeapPush(&hp, 3);
// HeapPush(&hp, 6);
// HeapPush(&hp, 20);
// HeapPush(&hp, 64);
// HeapPush(&hp, 10);
// HeapPush(&hp, 42);
//
// int k = 0;
// scanf("%d", &k);
//
// while (!HeapEmpty(&hp) && k--)
// {
// printf("%d ", HeapTop(&hp));
// HeapPop(&hp);
// }
// printf("\n");
// return 0;
//}void HeapSort(int* a, int n)
{for (int i = 1; i < n; ++i){AdjustUp(a, i);}
} int main()
{int a[10] = { 2,5,7,6,8,0,9,1,4,3};HeapSort(a, 10);return 0;
}结尾：
在这里我们讲解的堆的实现操作还有一部分的堆排序的知识，但是堆排序真正复杂的地方并不在这里，再往后我们还要学习并且计算它的时间复杂度等，这才是复杂的地方。最后希望这篇博客可以为大家带来帮助。
查看全文
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.dgrt.cn/a/2033237.html
如若内容造成侵权/违法违规/事实不符，请联系一条长河网进行投诉反馈，一经查实，立即删除！
相关文章：
数据结构——二叉树与堆
作者：几冬雪来 时间： 内容：二叉树与堆内容讲解 目录
前言：
1.完全二叉树的存储：
2.堆的实现：
1.创建文件：
2.定义结构体：
3.初始化结构体：
4.扩容空间与扩容……
编程日记2023/3/24 23:23:09
Redis的十大常见应用场景
一、缓存 作为Key-Value形态的内存数据库，Redis 最先会被想到的应用场景便是作为数据缓存。目前这几乎是所有中大型网站都在用的必杀技，合理的利用缓存不仅能够提升网站访问速度，还能大大降低数据库的压力，而使用 Redis 缓存数据也……
编程日记2023/3/24 23:22:59
创建数据库中，超详细常用的MySQL命令（含解析、图解与全部代码）
目录 系统命令行
MySQL命令行
数据库命令
数据表命令
建表并导入数据
表的其他操作 系统命令行
以下是在系统命令行，已管理员身份运行的情况下，MySQL的一些命令
1.这两条是关闭MySQL服务与开启MySQL服务的命令
net stop MySQL
net start MySQL80……
编程日记2023/3/24 23:22:58
【Oracle】Oracle错误 ora-12514 检查以及解决方法
问题
本地测试的时候，连接测试服务器上的Oracle数据库，报错如下： ORA-12514, TNS:listener does not currently know of service requested in connect descriptor 参考文章
stackoverflow参考文章
本地问题解决
1.查看Oracle当前监听器状……
编程日记2023/3/24 23:22:57
MySQL获取当前时间、年月、年月日
文章目录1.mysql获取当前时间（年月日 时分秒）2.mysql获取当前年月3.mysql获取当前年月日4.mysql获取当前年份5.mysql获取当前月份6.mysql获取当前日1.mysql获取当前时间（年月日 时分秒）
代码如下：
SELECT NOW();2.my……
编程日记2023/3/24 23:22:57
linux下安装mysql8
1、到指定目录下下载安装包
[rootVM-0-14-centos ~]# cd /usr/local/src 2、下载mysql8
[rootVM-0-14-centos src]# wget https://dev.mysql.com/get/Downloads/MySQL-8.0/mysql-8.0.20-linux-glibc2.12-x86_64.tar.xz 3、解压mysql8, 通过xz命令解压出tar包， 然后……
编程日记2023/3/24 23:22:54
Ubuntu安装redis及redis基本配置
一、安装redis
1、执行sudo apt-get update更新软件包
rootubuntu:~# sudo apt-get update2、执行sudo apt-get install redis-server，输入y 确认安装并使用空间 3、执行完成后，查看redis服务的状态，执行ps -ef|grep redis查看 或者 servic……
编程日记2023/3/24 23:22:51
还原Sql Server数据库BAK备份文件的三种方式及常见错误
第一种方法，使用Sql Server Management Studio还原
这是演示的是Sql Server 2008R2版本，不同版本可能有细微差别
右键点击数据库→还原数据库 在还原的源中选择源设备→点击选择框 在指定备份中点击添加→选择具体文件→确定→确定 勾选用于还原的备份……
编程日记2023/3/24 23:22:50
人工智能会给普通人带来哪些改变
最近人工智能太火了，很多人都听说了，尤其是大语言模型。可以让我们像和真人聊天一样，与AI对话，根据你所问的问题，AI可能像一个老师，像一个老人，像一个智者回答你的几乎所有问题。这也把有些人吓……
编程日记2023/3/24 23:22:29
【Python】更精美的俄罗斯方块开发指南（步骤已写）
文章目录前言一、游戏介绍二、源码剖析1.引入库2.读入数据总结前言
最近想找一些Python相关的游戏开发例子，正好在itch.io上闲逛看到这个俄罗斯方块项目，瞬间被惊艳到了。作者是 Mikhail ，项目(tetris_for_two)地址是： https://g……
编程日记2023/3/24 23:22:27
客快物流大数据项目（一百一十二）：初识Spring Cloud
文章目录
初识Spring Cloud
一、Spring Cloud简介
二、SpringCloud 基础架构图…
编程日记2023/4/16 14:51:11
C和C++中的struct有什么区别
区别一： C语言中： Struct是用户自定义数据类型（UDT）。 C语言中： Struct是抽象数据类型（ADT），支持成员函数的定义。
区别二：
C中的struct是没有权限设置的，……
编程日记2023/4/16 14:50:59
docker的数据卷详解
数据卷 数据卷是宿主机中的一个目录或文件，当容器目录和数据卷目录绑定后，对方修改会立即同步
一个数据卷可以同时被多个容器同时挂载，一个容器也可以被挂载多个数据卷
数据卷作用：容器数据持久化 /外部机器和容器间接通信 /容器……
编程日记2023/4/16 14:50:50
13、Qt生成dll-QLibrary方式使用
Qt创建dll，使用QLibrary类方式调用dll
一、创建项目
1、新建项目->其他项目->Empty qmake Project->Choose 2、输入项目名，选择项目位置，下一步 3、选择MinGW，下一步 4、完成 5、.pro中添加TEMPLATE subdirsÿ……
编程日记2023/4/16 14:50:38
基于mapreduce 的 minHash 矩阵压缩
Minhash作用： 对大矩阵进行降维处理，在进行计算俩个用户之间的相似度。
比如： 俩个用户手机下载的APP的相似度，在一个矩阵中会有很多很多的用户要比较没俩个用户之间的相似度是一个很大的计算任务 如果首先对这个矩阵降维处理&am……
编程日记2023/4/16 14:50:37
关于hashmap使用迭代器的问题
keySet获得的只是key值的集合，valueSet获得的是value集合，entryset获得的是键值对的集合。 package com.test2.test;import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Map.Entry;public class mapiterator……
编程日记2023/4/16 14:50:37
Hadoop入口FileSystem HDFS操作 本地文件合并到HDFS和HDFS文件合并
Hadoop 文件API的起点是FileSystem类。这是一个与文件系统交互的抽象类。存在不同的具体实现子类来处理HDFS和本地文件系统。
HDFS接口的FileSystem对象：
Configuration conf new Configuration();
FileSystem hdfs FileSystem.get(conf); HDFS直接操作&#x……
编程日记2023/4/16 14:50:36
combiner partitioner
combine是在map端进行的，是在patition之后 partitioner也是在map端进行的 combine 适用在每个map端进行简单的合并，同样也是继承Reduce类。…
编程日记2023/4/16 14:50:35
toString.indexOf(:)和subsTring
package com.test2.test;public class subStirngTest {public static void main(String[] args) {String sb"abcdefgh";String sc"abcd:efgh";int splitIndexsc.indexOf(":");//找到标识符的位置System.out.println(splitIndex);sb.substring(1)……
编程日记2023/4/16 14:50:35
Aprior 算法
Apriori 算法：（hadoop中实现） 第一步：统计项的频度 （用一个MR统计出来） 假设是一个矩阵 U1 app1 , app3
U2 app1 , app2 , app3
U3 app2 , app3 把矩阵看成一行行的向量
U1<app……
编程日记2023/4/16 14:50:34