树与堆：从数据结构基础到算法实践的全面解析

树
- 定义
- 基本概念
- 基本性质
- 定义结构
二叉树
- 定义
- 特点
- 满二叉树
- - 定义
  - 结点数
- 完全二叉树
- - 定义
  - 高度为 h 的完全二叉树的节点范围
  - 结点数为 N 的完全二叉树和满二叉树的高度
- 性质
二叉树的存储结构
- 顺序存储
- 链式结构
堆
- 定义
- 性质
- 小根堆
- 大根堆
堆的操作实现
- 代码全貌与功能介绍
堆排序
- 建堆
- - 方法 1 - - - 向上调整建堆
  - 方法 2 - - - 向下调整建堆
  - 方法 3 - - - 使用数组建堆
- 排序
- 完整排序过程
- 建堆时间复杂度
TOP-k 问题
总结

💻作者简介：曾与你一样迷茫，现以经验助你入门数据结构。
💡个人主页：@笑口常开xpr 的个人主页
📚系列专栏：硬核数据结构与算法
✨代码趣语：树的直观概念意味着我们对数据进行组织。
💪代码千行，始于坚持，每日敲码，进阶编程之路。
📦gitee 链接：gitee

在这里插入图片描述

堆作为计算机科学中一种重要的数据结构，在排序算法、优先队列和内存管理等领域有着广泛应用。本文将从 C 语言的角度出发，详细解析堆的实现原理、核心操作及其应用场景。

树

定义

树是一种 非线性 的数据结构，它是由 n（n>=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）棵互不相交的树的集合称为森林。

注意
1、树只有度的概念，有向图有入度和出度的概念，这一点应严格区分。
2、树的高度或深度是从 1 开始的，如上图树的高度是 4，如果是从 0 开始的，无法计算空树的高度。
3、数的结构是根朝上，叶朝下的。

基本性质

1、任何一棵树都是有根和子树构成的。
2、子树是不相交的。如果相交，会导致递归的死循环。
3、除了根结点外，每个结点有且仅有一个父结点。
4、一棵 N 个结点的树有 N - 1 条边。

定义结构

方法 1 - - - 已知树的度

#define N 5 //假设已知树的度为5
struct TreeNode
{struct TreeNode* a[N]; //指针数组int data;
};

方法 2 - - - 顺序表或链表

//链表节点结构体
typedef struct ListNode 
{TreeNode* data;        //指向树节点struct ListNode* next; //指向下一个链表节点
}ListNode;//树节点结构体
typedef struct TreeNode 
{int data;           //树节点数据ListNode* children; //指向子节点链表的头节点
}TreeNode;//树的结构体
typedef struct Tree 
{TreeNode* root; // 树的根节点
}Tree;

方法 3 - - - 左孩子右兄弟

typedef int DataType;
struct Node
{struct Node* firstChild1;  //第一个孩子结点struct Node* pNextBrother; //指向其下一个兄弟结点DataType data;             //结点中的数据域
};

在这里插入图片描述

二叉树

定义

一棵二叉树是结点的一个有限集合，该集合:

或者为空
由一个根结点加上两棵别称为左子树和右子树的二叉树组成。

特点

1、二叉树不存在度大于 2 的结点。
2、二叉树的子树有左右之分，次序不能颠倒。

二叉树只能有以下几种情况构成：
在这里插入图片描述

满二叉树

定义

一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。

结点数

如果一个二叉树的层数为 K，第 1 层的结点数为 2 ^ 0，第 2 层的结点数为 2 ^ 1，第 3 层的结点数为 2 ^ 2，以此类推，最后一层的结点数为 2 ^ (k-1)，结点总数是 (2 ^ k) - 1，则它就是满二叉树。
前 K - 1 层都是满的，最后一层要求是从左到右是连续的。
在这里插入图片描述

完全二叉树

定义

对于深度为 K 的，有 n 个结点的二叉树，当且仅当其每一个结点都与深度为 K 的满二叉树中编号从 1 至 n 的结点一一对应时称之为完全二叉树。满二叉树是一种特殊的完全二叉树。
在这里插入图片描述

高度为 h 的完全二叉树的节点范围

最多时为满二叉树，即第 1 层为 2 ^ 0 个，第 2 层为 2 ^ 1 个，依次类推，最后一层为 2 ^ (h - 1) 个，使用等比数列公式可得：1*(1 - 2 ^ h)/1-2=2 ^ h - 1。

最少时最后一层只有 1 个节点，即第 1 层为 2 ^ 0 个，第 2 层为 2 ^ 1 个，依次类推，倒数第 2 层有 2 ^ (h - 2) 个，对前面 h - 1 层使用等比数列公式可得：1*(1 - 2 ^ (h - 1))/ 1 - 2 = 2 ^ (h - 1) - 1。总共有 2 ^ (h - 1) - 1 + 1 = 2 ^ (h - 1) 个节点。

最多（最后一层最多 2 ^ (h - 1) 个，即满二叉树）：2 ^ h - 1
最少（最后一层最少 1 个）：2 ^ (h - 1)

结点数为 N 的完全二叉树和满二叉树的高度

满二叉树
高度为 h 的完全二叉树有 2 ^ h - 1 个节点，即 2 ^ h - 1 = N，h = log2(N+1)，约等于 log2(N)。

完全二叉树
高度为 h 的完全二叉树的节点范围：
最多：2 ^ h - 1
最少：2 ^ (h - 1)
最多：2 ^ h - 1 = N，h = log2(N+1)，约等于 log2(N)。
最少：2 ^ (h - 1)，h = log2N+1，约等于 log2(N)。

性质

1、若规定根结点的层数为 1，则一棵非空二叉树的 第 i 层上最多有 2^(i-1) 个结点。
2、若规定根结点的层数为 1，则 深度为 h 的二叉树的最大结点数是 2 ^ h - 1。
3、对任何一棵二叉树，如果度为 0 其叶结点个数为 n0, 度为 2 的分支结点个数为 n2，则有 n0＝n2＋1。完全二叉树的度为 1 的节点的个数要么是 1 要么是 0。
4、若规定根结点的层数为 1，具有 n 个结点的满二叉树的深度，h=log2(n + 1)。
(ps：log2(n+1) 是 log 以 2 为底，n + 1 为对数)
5、对于具有 n 个结点的完全二叉树，如果按照从上至下从左至右的数组顺序对所有结点从 0 开始编号，则对于序号为 i 的结点有：
（1）若 i > 0，i 位置结点的双亲序号：( i - 1 ) / 2；i = 0，i 为根结点编号，无双亲结点。
（2）若 2 i + 1 = n ，否则无左孩子
（3）若 2 i + 2 = n ，否则无右孩子

二叉树的存储结构

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

顺序存储

顺序结构存储就是使用 数组来存储，一般使用数组 表示完全二叉树，因为不是完全二叉树会有空间的浪费。只有堆才会使用数组来存储。二叉树顺序存储在物理结构上是一个数组，在逻辑结构上是一颗二叉树。

表示二叉树的值在数组位置中父子下标关系
父母和孩子下标的关系：parent = (child - 1) / 2

父母和左孩子下标的关系：leftchild = parent * 2 + 1

父母和右孩子下标的关系：rightchild = parent * 2 + 2
在这里插入图片描述

链式结构

二叉树的链式存储结构是指用链表来表示一棵二叉树，即用链来指示元素的逻辑关系。通常的方法是链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址。链式结构又分为二叉链和三叉链。

堆

定义

堆是一种特殊的完全二叉树数据结构。堆使用数组来存储，即顺序存储方式。

性质

结构性
堆必须是完全二叉树，即除了最后一层外，其他层的节点都是满的，且最后一层的节点靠左排列。
有序性
1、堆中某个结点的值总是不大于或不小于其父结点的值。
2、堆总是一棵完全二叉树。

注意：堆不一定有序，没有限制左右孩子之间的大小关系。

小根堆

树中所有的父亲都小于或等于孩子。堆顶的数据最小。

大根堆

树中所有的父亲都大于或等于孩子。堆顶的数据最大。

堆的操作实现

代码全貌与功能介绍

整个堆由三个主要文件构成：Heap.h、Heap.c 和 test.c。这种多文件的架构设计，有助于将不同功能模块分离，提高代码的可读性、可维护性与可扩展性。

Heap.h

Heap.h 包含了堆所需的头文件引用、常量定义以及函数声明。

test.c

test.c 是堆的主逻辑文件，负责处理用户输入和代码流程的控制。

Heap.c

Heap.c 则实现了堆的具体功能函数。

下面展示完整代码。

读者可以将这段代码复制到自己的编译器中运行。

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 HeapDestory(HP* php);//堆的插入
void HeapPush(HP* php, HPDataType x);//交换数据
void Swap(HPDataType* p1, HPDataType* p2);//向上调整
void AdjustUP(HPDataType* a, int child);//删除堆顶的数据
//挪动删除:
//效率低下
//父子兄弟关系全乱了
//间接删除
void HeapPop(HP* php);//输出数据
void HeapPrint(HP* php);//向下调整
void AdjustDown(HPDataType* a, int n, int parent);//输出堆顶元素
HPDataType HeapTop(HP* php);//堆的元素个数
int HeapSize(HP* php);//堆是否为空
bool HeapEmpty(HP* php);//将数据保存到文件中
void HeapSave(HP* php);//从文件中读取数据
void HeapLoad(HP* php);//函数指针
void HeapPushMiddle(void(*pf)(HP* php, HPDataType x), HP* php);void HeapMiddle(HPDataType(*pf)(HP* php), HP* php, int num);

test.c

#include "Heap.h"
void menu()
{printf("*********************************************\n");printf("*****   0. HeapExit     1. HeapPush    ******\n");printf("*****   2. HeapPop      3. HeapPrint   ******\n");printf("*****   4. HeapTop      5. HeapSize    ******\n");printf("*****   6. HeapEmpty                   ******\n");printf("*********************************************\n");
}
void test()
{int input = 0;HP hp;HeapInit(&hp);do{menu();printf("请输入你想要进行的操作:>");scanf("%d", &input);switch (input){case 0:HeapSave(&hp);HeapDestory(&hp);break;case 1:HeapPushMiddle(HeapPush, &hp);break;case 2:HeapPop(&hp);HeapPrint(&hp);break;case 3:HeapPrint(&hp);break;case 4:HeapMiddle(HeapTop, &hp, 4);break;case 5:HeapMiddle(HeapSize, &hp, 5);break;case 6:HeapMiddle(HeapEmpty, &hp, 6);break;default:printf("输入无效,请重新输入\n");break;}} while (input);
}
int main()
{test();return 0;
}

Heap.c

#define _CRT_SECURE_NO_WARNINGS 1 
#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;HeapLoad(php);
}void HeapSave(HP* php)
{assert(php);FILE* pf = fopen("Heap.txt", "w");if (pf == NULL){perror("fopen fail");return;}int i = 0;for (i = 0; i < php->size; i++){fprintf(pf, "%d ", php->a[i]);}fclose(pf);pf = NULL;printf("保存文件成功\n");
}
void HeapLoad(HP* php)
{assert(php);FILE* pf = fopen("Heap.txt", "r");if (pf == NULL){perror("Load fail");return;}int num = 0;int index = 0;while (fscanf(pf, "%d", &num) == 1){HeapPush(php, num);}fclose(pf);pf = NULL;
}void Swap(HPDataType* p1, HPDataType* p2)
{HPDataType tmp = *p1;*p1 = *p2;*p2 = tmp;
}void HeapPush(HP* php, HPDataType x)
{assert(php);if (php->capacity == php->size){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);
}
//大根堆
//除了child这个位置,前面的数据构成了堆
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 AdjustDown(HPDataType* a, int n, int parent)
{//最坏log2N(堆的高度)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 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 AdjustDown(HPDataType* a, int n, int parent)
//{
//	//最坏log2N(堆的高度)
//	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(!HeapEmpty(php));assert(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];
}int HeapSize(HP* php)
{assert(php);return php->size;
}bool HeapEmpty(HP* php)
{assert(php);return php->size == 0;
}
void HeapMiddle(HPDataType(*pf)(HP* php), HP* php, int num)
{assert(php);if (num == 4){int ret = pf(php);printf("堆顶元素是:%d\n", ret);}else if (num == 5){int ret = pf(php);printf("堆的元素个数是:%d\n", ret);}else{bool ret = pf(php);if (ret == true){printf("堆是空\n");}else{printf("堆不是空\n");}}
}void HeapDestory(HP* php)
{assert(php);free(php->a);php->a = NULL;php->capacity = 0;php->size = 0;
}void HeapPushMiddle(void(*pf)(HP* php, HPDataType x), HP* php)
{assert(php);int x = 0;printf("请输入你想要插入的数字:>");scanf("%d", &x);pf(php, x);HeapPrint(php);
}void HeapPrint(HP* php)
{assert(php);int i = 0;for (i = 0; i < php->size; i++){printf("%d ", php->a[i]);}printf("\n");
}

注意
上面是大根堆的代码，如果想要改成小根堆的代码只需将 Heap.c 中的大根堆的两个函数代码注释，再将小根堆的代码取消注释即可。如下两段代码所示：

大根堆

//大根堆
//除了child这个位置,前面的数据构成了堆
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 AdjustDown(HPDataType* a, int n, int parent)
{//最坏log2N(堆的高度)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 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 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;}}
}

堆排序

在使用堆排序之前应先将数组中的元素先建成堆，然后进行排序。

建堆

这里如果要排升序，推荐建大堆，假如建小堆，第一个元素最小，但如果再进行排序，后面的每一个元素都需要重新建堆，时间复杂度太高，所以 排升序时，应该建大堆。下面以建大堆为例。

方法 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;}}
}
void HeapSort(int* a, int n)
{int i = 0;for (i = 1; i < n; i++){AdjustUP(a, i);}
}

方法 2 - - - 向下调整建堆

void AdjustDown(HPDataType* a, int n, int parent)
{//最坏log2N(堆的高度)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 HeapSort(int* a, int n)
{int i = 0;for (i = (n - 1 - 1) / 2; i >= 0; i--)//n-1是最后数字的下标，然后是parent = (child-1)/2的公式{AdjustDown(a, n, i);}
}

方法 3 - - - 使用数组建堆

typedef struct Heap
{HPDataType* a;int size;int capacity;
}HP;
//使用数组建堆
void HeapInitArray(HP* php, int* a, int n)
{assert(php);php->a = (HPDataType*)malloc(sizeof(HPDataType) * 4);if (php->a == NULL){perror("malloc fail");return;}php->size = n;php->capacity = n;//建堆int i = 0;for (i = (n - 2) / 2; i >= 0; i--){AdjustDown(php->a, php->size, i);}
}

排序

void AdjustDown(HPDataType* a, int n, int parent)
{//最坏log2N(堆的高度)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 HeapSort(int* a, int n)
{int end = n - 1;while (end > 0){Swap(&a[end], &a[0]);AdjustDown(a, end, 0);end--;}
}

完整排序过程

#include<stdio.h>
typedef int HPDataType;
void Swap(HPDataType* p1, HPDataType* p2)
{HPDataType tmp = *p1;*p1 = *p2;*p2 = tmp;
}
void AdjustDown(HPDataType* a, int n, int parent)
{//最坏log2N(堆的高度)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 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 HeapSort(int* a, int n)
{//向上调整建堆int i = 0;for (i = 1; i < n; i++){AdjustUP(a, i);}//堆排序int end = n - 1;while (end > 0){Swap(&a[end], &a[0]);AdjustDown(a, end, 0);end--;}//建堆 --- 向下调整建堆//时间复杂度:O(N-log2(N)) = O(N)//int i = 0;//for (i = (n - 1 - 1) / 2; i >= 0; i--)//n-1是最后数字的下标//{//	AdjustDown(a, n, i);//}//int end = n - 1;//while (end > 0)//{//	Swap(&a[end], &a[0]);//	AdjustDown(a, end, 0);//	end--;//}
}
void test1()
{int a[] = { 1,3,5,7,6,4,9,2,8,0 };//对数组排序int sz = sizeof(a) / sizeof(a[0]);HeapSort(a, sz);int i = 0;//for (i = sz - 1; i >= 0; i--)//{//	printf("%d ", a[i]);//}for (i = 0; i < sz; i++){printf("%d ", a[i]);}printf("\n");
}
int main()
{test1();return 0;
}

在这里插入图片描述
时间复杂度：O(n*log2(n))

建堆时间复杂度

因为堆是完全二叉树，而满二叉树也是完全二叉树，这里使用满二叉树来证明 (时间复杂度本来看的就是近似值，多几个结点不影响最终结果)。
在这里插入图片描述
第 1 层有 2 ^ 0 个节点，需要向下移动 h - 1 层。
第 2 层有 2 ^ 1 个节点，需要向下移动 h - 2 层。
第 3 层有 2 ^ 2 个节点，需要向下移动 h - 3 层。
…
第 h - 2 层有 2 ^ ( h - 3 ) 个节点，需要向下移动 2 层。
第 h - 1 层有 2 ^ ( h - 2 ) 个节点，需要向下移动 1 层。
则需要移动结点总的移动步数为：
T(n) = 2 ^ 0 * (h-1) + 2 ^ 1 * (h-2)+2 ^ 2 * (h-3) +…+ 2 ^ (h-3) * 2+2 ^ (h-2)*1 （1）
2 * T(n) = 2 ^ 1 * (h-1) + 2 ^ 2 * (h-2)+2 ^ 3 * (h-3) +…+ 2 ^ (h-2) * 2+2 ^ (h-1)*1 （2）
（2） - （1）得：
T(n) = 2 ^ h - 1 - h
n = 2 ^ h - 1
h = log2(n+1)
T(n)=n- log2(n+1)
所以 T(n) 约等于 n。建堆的时间复杂度约为 O(N)。

TOP-k 问题

求数据结合中前 K 个最大的元素或者最小的元素，一般情况下数据量都比较大。最佳的方式就是用堆排序来解决，基本思路如下：
1、用数据集合中前 K 个元素来建堆
（1）前 k 个最大的元素，则建小堆
（2）前 k 个最小的元素，则建大堆
2、用剩余的 N - K 个元素依次与堆顶元素来比较，不满足则替换堆顶元素。
3、将剩余 N - K 个元素依次与堆顶元素比完之后，堆中剩余的 K 个元素就是所求的前 K 个最小或者最大的元素。

下面以随机生成 10000 个数据为例使用堆排序找出最大的前 K 个数。

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
#include <time.h>
void Swap(int* p1, int* p2)
{int tmp = *p1;*p1 = *p2;*p2 = tmp;
}
void AdjustDown(int* a, int n, int parent)
{//最坏log2N(堆的高度)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 PrintTopK(const char* file, int k)
{//1. 建堆 --- 用a中前k个元素建堆int* topk = (int*)malloc(sizeof(int) * k);if (topk == NULL){perror("malloc fail");return;}FILE* fout = fopen(file, "r");if (fout == NULL){perror("fopen fail");return;}//读取文件中的前k个数据建小堆int i = 0;for (i = 0; i < k; i++){fscanf(fout, "%d", &topk[i]);}//建堆for (i = (k - 2) / 2; i >= 0; i--){AdjustDown(topk, k, i);}//2.将剩余n-k个元素依次与堆顶元素交换,不满则则替换int val = 0;int ret = fscanf(fout, "%d", &val);while (ret != EOF){if (val > topk[0]){topk[0] = val;AdjustDown(topk, k, 0);}ret = fscanf(fout, "%d", &val);}for (i = 0; i < k; i++){printf("%d ", topk[i]);}printf("\n");free(topk);fclose(fout);fout = NULL;
}
void CreateNData()
{int n = 10000;srand(time(0));const char* file = "num.txt";FILE* fin = fopen(file, "w");if (fin == NULL){perror("file fail");return;}for (size_t i = 0; i < n; ++i){int x = rand() % 10000;fprintf(fin, "%d\n", x);}PrintTopK(file, 10);fclose(fin);fin = NULL;
}
int main()
{//CreateNData();PrintTopK("num.txt", 10);return 0;
}

在这里插入图片描述

总结

树与堆的本质是对数据的层次化与有序化组织。树提供了非线性数据的基础建模方式，而堆通过完全二叉树与有序性的结合，实现了极值操作的高效性。从理论概念到代码实现，二者均体现了数据结构 “逻辑结构” 与 “存储结构 ” 的紧密关联，是算法设计中不可或缺的基础模块。

树 与 堆：从 数 据 结 构 基 础 到 算 法 实 践 的 全 面 解 析

树 与 堆：从 数 据 结 构 基 础 到 算 法 实 践 的 全 面 解 析

树

定 义

基 本 概 念

基 本 性 质

定 义 结 构

二 叉 树

定 义

特 点

满 二 叉 树

定 义

结 点 数

完 全 二 叉 树

定 义

高 度 为 h 的 完 全 二 叉 树 的 节 点 范 围

结 点 数 为 N 的 完 全 二 叉 树 和 满 二 叉 树 的 高 度

性 质

二 叉 树 的 存 储 结 构

顺 序 存 储

链 式 结 构

堆

定 义

性 质

小 根 堆

大 根 堆

堆 的 操 作 实 现

代 码 全 貌 与 功 能 介 绍

堆 排 序

建 堆

方 法 1 - - - 向 上 调 整 建 堆

方 法 2 - - - 向 下 调 整 建 堆

方 法 3 - - - 使 用 数 组 建 堆

排 序

完 整 排 序 过 程

建 堆 时 间 复 杂 度

TOP-k 问 题

总 结

相关资讯

热文排行

最新新闻

推荐新闻

热搜词

树与堆：从数据结构基础到算法实践的全面解析

树与堆：从数据结构基础到算法实践的全面解析

定义

基本概念

基本性质

定义结构

二叉树

定义

特点

满二叉树

定义

结点数

完全二叉树

定义

高度为 h 的完全二叉树的节点范围

结点数为 N 的完全二叉树和满二叉树的高度

性质

二叉树的存储结构

顺序存储

链式结构

定义

性质

小根堆

大根堆

堆的操作实现

代码全貌与功能介绍

堆排序

建堆

方法 1 - - - 向上调整建堆

方法 2 - - - 向下调整建堆

方法 3 - - - 使用数组建堆

排序

完整排序过程

建堆时间复杂度

TOP-k 问题

总结