中国建设银行邵阳分行网站,浙江网络公司网站建设,网站备案人的法律风险,精美网站设计作者#xff1a;几冬雪来 时间#xff1a; 内容#xff1a;二叉树与堆内容讲解 目录
前言#xff1a;
1.完全二叉树的存储#xff1a;
2.堆的实现#xff1a;
1.创建文件#xff1a;
2.定义结构体#xff1a;
3.初始化结构体#xff1a;
4.扩容空间与扩容… 作者几冬雪来 时间 内容二叉树与堆内容讲解 目录
前言
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.htypedef 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.hvoid 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;
}
结尾 在这里我们讲解的堆的实现操作还有一部分的堆排序的知识但是堆排序真正复杂的地方并不在这里再往后我们还要学习并且计算它的时间复杂度等这才是复杂的地方。最后希望这篇博客可以为大家带来帮助。
