目录
一, 树
1.2 树的相关概念
1.3 树的表示
1.4 树在实际中的运用(表示文件系统的目录树结构)
二, 二叉树
2.1二叉树概念
三,特殊的二叉树
1. 满二叉树
2. 完全二叉树
3. 1 二叉树的性质
3. 2 二叉树的存储结构
1. 顺序存储
3. 3 堆的概念及结构
3. 4 堆的实现(以大堆为例)
1. Heap.h 结构体创建 + 函数声明
2. Heap.c 函数实现
3. HeapText.c 测试
4. 向上调整算法(以大堆为例)
2. 堆的删除数据(大堆)
3. 向下调整算法(大堆)
3. 5 堆的应用
1. Top-K问题
2. 堆排序
3. 堆排序:建堆时间复杂度O(N)证明
一,树
- 有一个特殊的结点,称为根结点,根节点没有前驱结点。
- 除根节点外,其余结点被分成M(M>0)个互不相交的集合T1、T2、……、Tm,其中每一个集合Ti(1<= i <= m)又是一棵结构与树类似的子树。每棵子树的根结点有且只有一个前驱,可以有0个或多个后继结点,因此,树是递归定义的。
注意:树形结构中,子树之间不能有交集,否则就不是树形结构
1.2 树的相关概念
节点的度:一个节点含有的子树的个数称为该节点的度;如上图: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)棵互不相交的树的集合称为森林;
1.3 树的表示
typedef int DataType;
struct Node
{structNode*_firstChild1; // 第一个孩子结点structNode*_pNextBrother; // 指向其下一个兄弟结点DataType_data; // 结点中的数据域
};
如图:
1.4 树在实际中的运用(表示文件系统的目录树结构)
二, 二叉树
2.1二叉树概念
1. 或者为空。2. 由一个根节点加上两棵别称为左子树和右子树的二叉树组成
可以看出:
1. 二叉树不存在度大于2的结点。2. 二叉树的子树有左右之分,次序不能颠倒,因此二叉树是有序树注意:对于任意的二叉树都是由以下几种情况复合而成的:
三,特殊的二叉树
1. 满二叉树
:一个二叉树,如果每一个层的结点数都达到最大值,则这个二叉树就是满二叉树。也就是说,如果一个二叉树的层数为K,且结点总数是2^k - 1,则它就是满二叉树。
2. 完全二叉树
:完全二叉树是效率很高的数据结构,完全二叉树是由满二叉树而引出来的。对于深度为K的,有n个结点的二叉树,当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。要注意的是满二叉树是一种特殊的完全二叉树。
如图:
3. 1 二叉树的性质
1. 若规定根节点的层数为1,则一棵非空二叉树的第i层上最多有2^(i - 1)个结点
2. 若规定根节点的层数为1,则深度为h的二叉树的最大结点数是n = 2^h - 1。
3.若规定根节点的层数为1,具有n个结点的满二叉树的深度,h = log2 (n + 1)。
4. 对任何一棵二叉树, 如果度为0其叶结点个数为K,度为2的分支结点为Z,则有K = Z + 1。
5. 对于具有n个结点的完全二叉树,如果按照从上至下从左至右的数组顺序对所有节点从0开始编号,则对于序号为i的结点有:
- 若i>0,i位置节点的双亲序号:(i-1)/2;i=0,i为根节点编号,无双亲节点
- 若2i+1<n, 左孩子序号: 2i+1, 2i+1>=n否则无左孩子
- 若2i+1+1<n,右孩子序号:2i+1+1,2i+2>=n否则无右孩子
如图:
3. 2 二叉树的存储结构
1. 顺序存储
3. 3 堆的概念及结构
概念:言简意赅的说,父亲的值大于孩子,就叫大堆; 反之,叫小堆。
- 堆中某个节点的值总是不大于或不小于其父节点的值;
- 堆总是一棵完全二叉树。
3. 4堆的实现(以大堆为例)
注:向上,下调整算法和删除堆数据单独详解
1. Heap.h 结构体创建 + 函数声明
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>typedef int HeapDateType;
typedef struct Heap {HeapDateType* a;int size;int capacity;
}HP;// 小堆
// 堆初始化
void HeapInit(HP* hp);
// 插入数据,并自动调整数据
void HeapPush(HP* hp, HeapDateType x);
// 对堆空间扩容
void Heap_add_room(HP* hp);
// 删除数据
void HeapPop(HP* hp);
// 销毁数据
void HeapDestroy(HP* hp);
// 打印二叉数数据
void HeapPrint(HP* hp);
// 向下调整数据
void HeapAjustDown(int* a, int size, int parent);
// 向上调整数据
void HeapAjustUp(int* a, int child);
// 交换位置
void Swap(int* n1, int* n2);
// 判断堆是否为空
bool HeapEmpty(HP* hp);
// 返回堆顶元素
HeapDateType HeapTop(HP* hp);
2. Heap.c 函数实现
#pragma once
#include"Heap.h"
//二叉树初始化
void HeapInit(HP* hp) {assert(hp);hp->a = NULL;hp->size = hp->capacity = 0;
}// 销毁数据
void HeapDestroy(HP* hp)
{assert(hp);free(hp->a);/*hp->a = NULL; // hp 首先是在栈上的变量,数据在函数完成后自动回收,所以不用担心野指针free(hp);*/hp->size = hp->capacity = 0;
}
// 打印二叉数
void HeapPrint(HP* hp)
{assert(hp);assert(!HeapEmpty(hp));for (int i = 0; i < hp->size; i++){printf("%d ", hp->a[i]);}printf("\n");
}// 删除数据
void HeapPop(HP* hp)
{assert(hp);assert(!HeapEmpty(hp));//交换堆顶, 堆底数据Swap(&hp->a[0], &hp->a[hp->size - 1]);hp->size--; // 没有减一// 再向下调整HeapAjustDown(hp->a, hp->size, 0);
}// 插入数据,并自动调整数据
void HeapPush(HP* hp, HeapDateType x) {assert(hp);if (hp->size == hp->capacity){Heap_add_room(hp);}hp->a[hp->size++] = x;// 向上调整HeapAjustUp(hp->a, hp->size - 1);// 输入最后一个有效数字的下标
}// 向下调整
void HeapAjustDown(int *a, int size, int parent)
{assert(a);int child = 2 * parent + 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 = 2 * parent + 1;}else{break;}}
}
// 向上调整数据
void HeapAjustUp(int * a, int child) // 孩子下标
{assert(a);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 Swap(int* n1, int* n2)
{int tmp = *n1;*n1 = *n2;*n2 = tmp;
}
// 判断堆是否为空
bool HeapEmpty(HP* hp)
{assert(hp);return hp->size == 0;
}void Heap_add_room(HP* hp)
{int newcapacity = hp->capacity == 0 ? 4 : hp->capacity * 2;HeapDateType* tmp = (HeapDateType*)realloc(hp->a, sizeof(HeapDateType) * newcapacity);if (tmp == NULL){perror("realloc");exit(-1);}hp->a = tmp;hp->capacity = newcapacity;
}HeapDateType HeapTop(HP* hp)
{assert(hp && !HeapEmpty(hp));return hp->a[0];
}
3. HeapText.c 测试
#pragma once
#include"Heap.h"
void text()
{int b[6] = {34, 32, 31, 12, 3, 28};HP hp;HeapInit(&hp);for (int i = 0; i < 6; i++){HeapPush(&hp, b[i]);}HeapPrint(&hp);HeapPush(&hp, 56);HeapPrint(&hp);HeapPush(&hp, 16);HeapPrint(&hp);HeapDestroy(&hp);
}
4. 向上调整算法(以大堆为例)
我们可以知道堆的物理存储是数组,为了保持堆的性质,所以堆插入只允许最后插入,而这时需要对插入的数据进行位置调整,以保持小(或大)堆。
parent下标: (child - 1) / 2
代码:
// 向上调整数据
void HeapAjustUp(int * a, int child) // 孩子下标
{assert(a);int parent = (child - 1) / 2;while (child > 0) // 不能为负数,为0时已经到堆顶了{ // 就2种情况,要么需要调整,要么呆在原地。if (a[child] > a[parent]) // 大的替换{//交换Swap(&a[child], &a[parent]);child = parent; // 孩子移动到父亲位置parent = (child - 1) / 2; // 父亲结点移动到其父亲的结点}else {break;}}
}
2. 堆的删除数据(大堆)
3. 向下调整算法(大堆)
// 向下调整
void HeapAjustDown(int *a, int size, int parent)
{assert(a);int child = 2 * parent + 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 = 2 * parent + 1;}else{break;}}
}
排大堆你会了吗?那小堆怎么排呢?我们可以这么想,向上调整算法目的是将大的孩子送上去,向下算法目的也是将大的孩子向堆高层送,所以将他们的判断方法取小于就行。
3. 5 堆的应用
1. Top-K问题
TOP-K问题:即求数据结合中前K个最大的元素或者最小的元素,一般情况下数据量都比较大。
- 前k个最大的元素,则建小堆
- 前k个最小的元素,则建大堆
2. 用剩余的N-K个元素依次与堆顶元素来比较,不满足则替换堆顶元素,将剩余N-K个元素依次与堆顶元素比完之后,堆中剩余的K个元素就是所求的前K个最小或者最大的元素。
例子:求1000个数据中最大10个数。
- 第一步: 数组前10个数据用来建立10个值的小堆。
代码:
// 创建一个堆HP hp;HeapInit(&hp);// 完成前K个的初始化for (int i = 0; i < K; i++){HeapPush(&hp, ps[i]); // 将小的向上调整}
- 第二步: 如果数组中的值大于堆顶,则进入堆中,调整数据。(2种方法)
1. 方法一:
2. 方法二: 代码:
// 开始逐步替换里面的数for (int i = K; i < n; i++){if (ps[i] > HeapTop(&hp)){hp.a[0] = ps[i]; // 方法一: 只调用一次函数(更优)HeapAjustDown(hp.a, hp.size, 0);/*HeapPop(&hp); // 方法二: 调用三次函数HeapPush(&hp, ps[i]);*/}}
最后代码如下:
void PrintTok(HeapDateType *ps, int n, int K)
{// 创建一个堆HP hp;HeapInit(&hp);// 完成前K个的初始化for (int i = 0; i < K; i++){HeapPush(&hp, ps[i]); // 将小的向上调整}// 开始逐步替换里面的数for (int i = K; i < n; i++){if (ps[i] > HeapTop(&hp)){hp.a[0] = ps[i]; // 方法一: 只调用一次函数(更优)HeapAjustDown(hp.a, hp.size, 0);/*HeapPop(&hp); // 方法二: 调用三次函数HeapPush(&hp, ps[i]);*/}}// 寻找完后开始打印这前k个数HeapPrint(&hp);
}
void text2() { // 测试函数int n = 10000; // 从10000个数据中找出前10个HeapDateType* a = (HeapDateType*)malloc(sizeof(HeapDateType) * n);if (a == NULL){printf("malloc fail");exit(-1);}srand(time(0)); // 准备随机数int K = 10;for (int i = 0; i < n; i++){a[i] = rand() % 10000; // 产生随机数录入用例数组}a[2] = 10000 + 10;a[3] = 10000 + 9;a[2353] = 10000 + 8;a[5678] = 10000 + 7;a[2324] = 10000 + 6;a[9999] = 10000 + 5;a[3435] = 10000 + 4;a[3432] = 10000 + 3;a[234] = 10000 + 2;a[34] = 10000 + 1;PrintTok(a, n, K);
}
2. 堆排序
我们通过TOPK算法求出了最大的前10个,但我们无法知道前10个的具体排名,而这时堆排序可以很好的解决这个问题。
思路:
- 升序:建大堆
- 降序:建小堆
- 第一步:建堆。假设我们用TopK算法求出了最大的前5名,我们知道数组已经是小堆形式了,这时需要我们进行把小堆转化为大堆,这样也就完成了建堆操作。
建堆的时间复杂度:O(N) ----- 等会证明
过程图如下:
代码实现:
for (int parent = (size - 1- 1) / 2; parent >= 0; parent--){HeapAjustDown(a, size, parent);}
- 第二步:删除数据向下调(之前我也不理解,但画很容易理解)
以逻辑结构视角:
以物理结构视角:
全部代码:
// 排升序 0 -> 10
void HeapSort(HeapDateType* a, int size)
{ // 1. 建堆for (int parent = (size - 1- 1) / 2; parent >= 0; parent--){HeapAjustDown(a, size, parent);}// 2. 排序for (int end = size - 1; end >= 0; end--) {Swap(&a[end], &a[0]);HeapAjustDown(a, end, 0);}
}
3. 堆排序:建堆时间复杂度O(N)证明
因为堆是完全二叉树,而满二叉树也是完全二叉树,此处为了简化使用满二叉树来证明(时间复杂度本来看的 就是近似值,多几个节点不影响最终结果):
结语
本小节就到这里了,感谢小伙伴的浏览,如果有什么建议,欢迎在评论区评论,如果给小伙伴带来一些收获请留下你的小赞,你的点赞和关注将会成为博主创作的动力。