当前位置：首页 > news >正文

做弹幕网站全球搜索引擎市场份额

news 2025/8/19 22:08:21

做弹幕网站,全球搜索引擎市场份额,高权重网站做员会来顶排名,北京朝阳区小区目录一、树概念及结构二、二叉树树概念及结构特殊的二叉树三、堆的概念及结构四、堆的创建 1、声明结构体 2、初始化 3、销毁 4、添加新元素 5、交换元素 6、向上调整 7、判断堆是否为空 8、移除堆顶元素 9、向下调整 10、获取堆元素个数五、使用堆排序…

一、树概念及结构

二、二叉树树概念及结构

特殊的二叉树

三、堆的概念及结构

四、堆的创建

1、声明结构体

2、初始化

3、销毁

4、添加新元素

5、交换元素

6、向上调整

7、判断堆是否为空

8、移除堆顶元素

9、向下调整

10、获取堆元素个数

五、使用堆排序

排降序建小堆

完整版：

Heap.h声明部分

Heap.c函数部分

text.c使用及测试部分

一、树概念及结构

树是一种非线性的数据结构，它是由n（n>=0）个有限结点组成一个具有层次关系的集合。把它叫做树是因 为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。

有一个特殊的结点，称为根结点，根节点没有前驱结点。
除根节点外，其余结点被分成M(M>0)个互不相交的集合T1、T2、……、Tm，其中每一个集合Ti(1 <= i <= m)又是一棵结构与树类似的子树。每棵子树的根结点有且只有一个前驱，可以有0个或多个后继。
因此，树是递归定义的
注意：树形结构中，子树之间不能有交集，否则就不是树形结构

节点的度：一个节点含有的子树的个数称为该节点的度；如上图：A的为6
叶节点或终端节点：度为0的节点称为叶节点；如上图：B、C、H、I...等节点为叶节点
非终端节点或分支节点：度不为0的节点；如上图：D、E、F、G...等节点为分支节点
双亲节点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点；如上图：A是B的父节点
孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点；如上图：B是A的孩子节点
兄弟节点：具有相同父节点的节点互称为兄弟节点；如上图：B、C是兄弟节点
树的度：一棵树中，最大的节点的度称为树的度；如上图：树的度为6
节点的层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推；
树的高度或深度：树中节点的最大层次；如上图：树的高度为4
堂兄弟节点：双亲在同一层的节点互为堂兄弟；如上图：H、I互为兄弟节点
节点的祖先：从根到该节点所经分支上的所有节点；如上图：A是所有节点的祖先
子孙：以某节点为根的子树中任一节点都称为该节点的子孙。如上图：所有节点都是A的子孙
森林：由m（m>0）棵互不相交的树的集合称为森林；

二、二叉树树概念及结构

二叉树是一个由n(n>=0)个结点构成的有限集合，其中该集合可以为空，这时称其为空二叉树；或者由一个根结点以及两个互不相交的左子树和右子树组成，且左右子树均为二叉树。在二叉树中，子树被明确区分为左子树和右子树，且它们的顺序不可颠倒。

值得注意的是，二叉树的定义具有递归性质，因为二叉树本身可以为空，根结点可以有空的左子树或空的右子树。
这使得二叉树与普通树有明显的区别，即使只有一棵子树存在，也需要明确指定它是左子树还是右子树。这是二叉树与树最主要的区别之一。
请注意，二叉树不同于一般的树，因为它的子树具有左右之分，并且顺序不能颠倒。因此，“二叉树是结点度为2的树”的说法是不正确的。

二叉树的基本形态包括以下五种：

特殊的二叉树

当涉及到二叉树的特殊类型时，有两个主要概念需要了解：满二叉树和完全二叉树。

满二叉树：满二叉树是一种特殊的二叉树，其特点是每个层级的结点数都达到最大值。具体来说，如果一个二叉树的深度为K，且结点总数为2^K - 1，那么它就是一个满二叉树。满二叉树的每一层都包含最大数量的结点，使得它具有很特殊的结构。
完全二叉树：完全二叉树是一种高效的数据结构，与满二叉树相关。一个二叉树如果在深度为K的情况下，其结点都与深度为K的满二叉树中的编号从1到n的结点一一对应，那么它就被称为完全二叉树。需要注意的是，满二叉树是完全二叉树的一个特殊情况。

性质

若规定根节点的层数为1，则一棵非空二叉树的第i层上最多有 $2^{i-1}$ 个结点。
若规定根节点的层数为1，则深度为h的二叉树的最大结点数是 $2^{h}-1$ 。
对任何一棵二叉树, 如果度为0其叶结点个数为 n0 , 度为2的分支结点个数为 n2 ,则有 n0 ＝n2 ＋1。
若规定根节点的层数为1，具有n个结点的满二叉树的深度，h=log以2为底，n+1的对数。
对于具有n个结点的完全二叉树，如果按照从上至下从左至右的数组顺序对所有节点从0开始编号，则对于序号为i的结点有：

若i>0，i位置节点的双亲序号：(i-1)/2；i=0，i为根节点编号，无双亲节点
若2i+1<n，左孩子序号：2i+1，2i+1>=n否则无左孩子
若2i+2<n，右孩子序号：2i+2，2i+2>=n否则无右孩子

三、堆的概念及结构

堆（Heap）是一种特殊的树状数据结构，通常用于实现优先队列和对数据进行排序。堆的主要特点是它是一棵树，其中每个节点的值满足特定的堆属性。在堆中，通常有两种主要类型：最大堆和最小堆。

最大堆（Max Heap）：在最大堆中，每个节点的值都不小于其子节点的值，即根节点的值最大。这意味着最大堆的最大元素总是位于根节点，而子树中的值递减。

最小堆（Min Heap）：在最小堆中，每个节点的值都不大于其子节点的值，即根节点的值最小。这意味着最小堆的最小元素总是位于根节点，而子树中的值递增。

堆的常见用途包括：

优先队列：堆可以用来实现高效的优先队列，使得可以快速访问和删除具有最高或最低优先级的元素。

堆排序：堆排序是一种高效的排序算法，它利用堆的性质来进行排序。它的时间复杂度为O(n log n)。

堆通常是以数组的形式来表示，其中父节点和子节点之间的关系通过数组索引来建立。具体来说，对于一个具有n个元素的堆，节点的索引从1到n编号，其中：

父节点的索引为i，则它的左子节点的索引为2i，右子节点的索引为2i + 1。
子节点的索引为i，则其父节点的索引为i/2。

这种数组表示方法使得堆的操作更加高效，因为它不需要使用额外的指针来表示树的结构。

四、堆的创建

本次以小堆举例进行讲解

1、声明结构体

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

HPDataType 被定义为 int 类型，表示堆中存储的数据类型。
创建堆的结构体Heap，定义别名为HP。
指针a指向堆的数组
size为堆的当前大小
capacity为堆的容量

2、初始化

void HeapInit(HP* php)
{assert(php);php->a = NULL;php->size = 0;php->capacity = 0;
}

assert 判断指针是否合法。
指向数组的指针 a 初始化为 NULL。
size 和 capacity 初始化为0。

3、销毁

void HeapDestroy(HP* php)
{assert(php);free(php->a);php->a = NULL;php->capacity = php->size = 0;
}

assert 判断指针是否合法。
释放数组空间，将 a 指针置空，同时将 capacity 和 size 设置为0。

4、添加新元素

void HeapPush(HP* php, HPDataType x)
{assert(php);if (php->size == php->capacity) {int newCapacity = php->capacity == 0 ? 4 : php->capacity * 2;HPDataType* tmp = (HPDataType*)realloc(php->a, newCapacity * sizeof(HPDataType));if (tmp==NULL) {perror("realloc fail");return;}php->a = tmp;php->capacity = newCapacity;}php->a[php->size] = x;php->size++;AdjustUp(php->a, php->size - 1);
}

assert 判断指针是否合法。
判断当前是否需要扩容，初始堆的容量为0，则为堆开辟四个HPDataType类型大小的空间，如果当前堆的大小size等于容量capacity，则将堆扩容为两倍原来大小的空间。
扩容失败，打印错误信息，结束函数
将扩容的空间赋值给指针a，更新容量capacity的大小。
将要增加的元素插入数组a中，更新size大小。
每次在堆中添加新元素时，小堆可能会被破坏，所以我们再添加新元素后，要在AdjustUp函数中判断是否需要进行向上调整。

5、交换元素

后续函数会经常用到，同一串代码放到函数里供其使用者调用比较好。

void Swap(HPDataType* p1, HPDataType* p2)
{HPDataType tmp = *p1;*p1 = *p2;*p2 = tmp;
}

6、向上调整

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;}}
}

首先通过当前的孩子节点child找到父节点parent。
当child大于0时，进行判断当前chilid是否需要调整
如果child位置元素小于parent位置元素，则通过Swap进行交换，然后新的孩子节点更新为parent位置，通过孩子节点更新新的父节点位置，然后继续比较和交换，直到不再需要交换为止。
如果当前孩子节点不小于当前的父节点，则结束循环，当前节点不需要向上调整。

7、判断堆是否为空

bool HeapEmpty(HP* php)
{assert(php);return php->size == 0;
}

8、移除堆顶元素

一般来说，堆的移除操作通常是移除堆顶元素，这样大堆小堆的性质保持不变，如果移除堆底会破坏堆的性质。

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);
}

assert 判断指针是否合法。
检查堆是否为空，为空则报错。
移除堆顶元素有两种方法，首选第二种方法，不需要重新建堆，节约时间。
首先交换堆顶堆尾，然后size减一完成删除，后续不会访问删除位置的元素，所以不释放内存空间也可以。
然后进行向下调整。

9、向下调整

向下调整是从第一个节点（父节点）开始向下调整，传入参数命名为parent

void AdjustDown(HPDataType* a, int size, int parent)
{int child = parent * 2 + 1;while (child < size) {if (child + 1 < size && a[child + 1] < a[child]) {child++;}if (a[child] < a[parent]) {Swap(&a[child], &a[parent]);parent = child;child = parent * 2 - 1;}else {break;}}
}

通过传入参数获取到当前的左子节点的位置。
当child位置小于数组元素个数时进行判断。
进入循环，首先判断检查右子节点是否存在并且比左子节点的值小，如果是，将 child 更新为右子节点的索引，以确保选择更小的子节点进行比较。
比较选定的子节点的值与父节点的值，如果子节点的值小于父节点的值，就交换它们。
更新parent为新的子节点位置，更新child为新的左子节点位置，然后继续比较和交换，直到不再需要交换为止。
如果当前子节点不小于当前父节点则停止循环。

10、获取堆元素个数

int HeapSize(HP* php)
{assert(php);return php->size;
}

五、使用堆排序

void HeapSort(int* a, int n)
{HP hp;HeapInit(&hp);// 时间复杂度：N*logNfor (int i = 0; i < n; ++i){HeapPush(&hp, a[i]);}// 时间复杂度：N*logNint i = 0;while (!HeapEmpty(&hp)){int top = HeapTop(&hp);a[i++] = top;HeapPop(&hp);}HeapDestroy(&hp);
}

可以使用这种方式，但有诸多弊端：

要先有一个堆,太麻烦。
空间复杂度+拷贝数据

排降序建小堆

所以我们要在传入的原数组上排降序，需要使用建小堆的方式向上调整。

void HeapSort(int* a, int n)
{// 建堆--向上调整建堆for (int i = 1; i < n; i++){AdjustUp(a, i);}int end = n - 1;while (end > 0){Swap(&a[0], &a[end]);// 再调整，选出次小的数AdjustDown(a, end, 0);--end;}
}

从根节点的子节点开始向上建堆，除了根节点以外，每个节点都进行向上调整。
定义堆的最后一个节点end为n-1
我们将堆的根节点（也就是最小值）与堆的最后一个元素交换，即将最小值放到排序尾部即为好的部分。接下来，通过调用AdjustDown函数，将堆的大小减一，再次将堆调整为最小堆。
重复while循环内部操作，直到整个数组排序完成。每次交换和堆的调整都会将最小的元素添加到已排序的部分，直到整个数组都有序。

HeapSort的时间复杂度为O(nlog(n))，它不需要额外的空间来存储数据，所以是一种原地排序算法。它在最坏情况下的性能仍然是O(nlog(n))，因此相对稳定，适用于大规模数据的排序。

我们也可以向下建堆：

倒着调整叶子节点不需要处理，从倒树第一个非叶子节点开始，即最后一个节点的父节点开始调整。

void HeapSort(int* a, int n)
{for (int i = (n - 1 - 1) / 2; i >= 0; --i){	AdjustDown(a, n, i);}int end = n - 1;while (end > 0){Swap(&a[0], &a[end]);// 再调整，选出次小的数AdjustDown(a, end, 0);--end;}
}

完整版：

Heap.h声明部分

#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 HeapInit(HP* php);
void HeapDestroy(HP* php);void AdjustUp(HPDataType* a, int child);
void HeapPush(HP* php, HPDataType x);
bool HeapEmpty(HP* php);
void AdjustDown(int* a, int n, int parent);
void HeapPop(HP* php);HPDataType HeapTop(HP* php);
int HeapSize(HP* php);

Heap.c函数部分

#include "Heap.h"void HeapInit(HP* php)
{assert(php);php->a = NULL;php->size = 0;php->capacity = 0;
}void HeapDestroy(HP* php)
{assert(php);free(php->a);php->a = NULL;php->capacity = php->size = 0;
}void Swap(HPDataType* p1, HPDataType* p2)
{HPDataType tmp = *p1;*p1 = *p2;*p2 = tmp;
}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) {int newCapacity = php->capacity == 0 ? 4 : php->capacity * 2;HPDataType* tmp = (HPDataType*)realloc(php->a, newCapacity * sizeof(HPDataType));if (tmp==NULL) {perror("realloc fail");return;}php->a = tmp;php->capacity = newCapacity;}php->a[php->size] = x;php->size++;AdjustUp(php->a, php->size - 1);
}bool HeapEmpty(HP* php)
{assert(php);return php->size==0;
}
void AdjustDown(HPDataType* a, int size, int parent)
{int child = parent * 2 + 1;while (child < size) {if (child + 1 < size && 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);assert(!HeapEmpty(php));return php->a[0];
}int HeapSize(HP* php)
{assert(php);return php->size;
}

text.c使用及测试部分

#define _CRT_SECURE_NO_WARNINGS 1
#include "Heap.h"void HeapSort(int* a, int n)
{// 建堆--向上调整建堆for (int i = 1; i < n; i++){AdjustUp(a, i);}// 建堆--向下调整建堆//for (int i = (n - 1 - 1) / 2; i >= 0; --i)//{//	AdjustDown(a, n, i);//}int end = n - 1;while (end > 0){Swap(&a[0], &a[end]);// 再调整，选出次小的数AdjustDown(a, end, 0);--end;}		
}int main()
{int a[] = { 7,8,3,5,1,9,5,4 };HeapSort(a, sizeof(a) / sizeof(int));for (int i = 0; i < 8; i++) {printf("%d  ", a[i]);}return 0;
}//---测试堆函数功能---
//int main()
//{
//	HP hp;
//	HeapInit(&hp);
//	int a[] = { 65,100,70,32,50,60 };
//	for (int i = 0; i < sizeof(a) / sizeof(int); ++i)
//	{
//		HeapPush(&hp, a[i]);
//	}
//	
//	while (!HeapEmpty(&hp))
//	{
//		int top = HeapTop(&hp);
//		printf("%d\n", top);
//		HeapPop(&hp);
//	}
//
//	return 0;
//}