C算法
数据结构：顺序结构二叉树与堆详解
本文详细介绍了树与二叉树的基本概念、术语及分类，重点讲解了顺序结构存储下的堆（Heap）。内容包括堆的结构定义、初始化、销毁、插入（向上调整）、删除堆顶（向下调整）及获取堆顶等功能实现。通过对比向上与向下调整算法的时间复杂度，得出向下调整更优的结论，并提供了完整的 C 语言代码示例，涵盖头文件声明、核心算法实现及测试用例。
本文详细介绍了树与二叉树的基本概念、术语及分类，重点讲解了顺序结构存储下的堆（Heap）。内容包括堆的结构定义、初始化、销毁、插入（向上调整）、删除堆顶（向下调整）及获取堆顶等功能实现。通过对比向上与向下调整算法的时间复杂度，得出向下调整更优的结论，并提供了完整的 C 语言代码示例，涵盖头文件声明、核心算法实现及测试用例。
树是一种非线性的数据结构，它是由 n（n>=0）个有限结点组成一个具有层次关系的集合。 具有以下特点：
除根结点外，其余结点被分成 M(M>0) 个互不相交的集合，每一 个集合又是 一棵结构与树类似的子树。每棵子树的根结点仅有一个前驱结点，但可以有多个互不相交的后驱结点。(若存在相交就是图了)
树的表示有很多种，最常用的便是孩子兄弟表示法，其很好地解决了结点和结点之间的关系。
struct TreeNode {
struct Node* child; // 左边开始的第一个孩子结点
struct Node* brother; // 指向其右边的下一个兄弟结点
int data; // 结点中的数据域
};
文件系统是计算机存储和管理文件的一种方式，它利用树形结构来组织和管理文件和文件夹。在文件系统中，树结构被广泛应用，它通过父结点和⼦结点之间的关系来表示不同层级的文件和文件夹之间的关联。
一棵二叉树是结点的一个有限集合，该集合由一个根结点加上两棵别称为左子树和右子树的二叉树组成或者为空。
特点：
如果每一个层的结点数都达到最大值或满足结点总数是 2^k-1 则这个二叉树就是满二叉树。 2^k-1 的公式推导：
总的结点数：2^0 + 2^1 + 2^2+……+2^(k-1) = 1 * (1 - 2^k) / (1 - 2) = 2^k-1
规定根结点的层数为 1:
顺序结构存储是使用数组来存储，在实现完全二叉树能减少空间浪费。
由于堆底层是用数组实现的，因此相似于顺序表，其结构定义如下：
typedef int HPDataType;
// 定义堆的结构
typedef struct HeapNode {
HPDataType* arr;
int size; // 有效数据个数
int capacity; // 容量
} HP;
这些代码实现已经在顺序表中介绍到。
// 堆的初始化
void HPInit(HP* php) {
assert(php);
php->arr = NULL;
php->size = php->capacity = 0;
}
// 堆的销毁
void HPDestroy(HP* php) {
assert(php);
if (php->arr) free(php->arr);
php->arr = NULL;
php->capacity = php->size = 0;
}
熟悉了堆的概念与结构后，我们清楚堆要不就是大根堆，要不就是小根堆。问题在于插入数据后，我们如何通过代码实现化成大根堆或者小根堆的形式？由此我们提出了向上 (下) 调整算法，也会带大家分析这两种算法哪种更好。
bool HPEmpty(HP* php) {
assert(php);
return php->size == 0;
}
删除堆顶数据后，如何让其再次成为大 (小) 根堆。
由此我们引入了向下调整算法。
前提：左右⼦树必须是⼀个堆，才能调整。
HPDataType HPTop(HP* php) {
assert(!HPEmpty(php));
return php->arr[0];
}
int HPSize(HP* php) {
assert(php);
return php->size;
}
根据大 O 表示法，则 O(n*log2n) -->详见算法复杂度篇章
根据大 O 表示法可见时间复杂度为 O(n)
因此向下调整算法的时间复杂度更优。
#define _CRT_SECURE_NO_WARNINGS 1
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
#include <time.h>
typedef int HPDataType;
// 定义堆的结构
typedef struct HeapNode {
HPDataType* arr;
int size; // 有效数据个数
int capacity; // 容量
} HP;
// 堆的初始化
void HPInit(HP* php);
// 堆的销毁
void HPDestroy(HP* php);
// 堆的插入数据
void HPPush(HP* php, HPDataType x);
// 删除堆顶数据
void HPPop(HP* php);
// 获取堆顶数据
HPDataType HPTop(HP* php);
// 判空
bool HPEmpty(HP* php);
// 求 size
int HPSize(HP* php);
// 向上调整
void AdjustUp(HPDataType* arr, int child);
// 向下调整
void AdjustDown(HPDataType* arr, int parent, int n);
// 交换
void Swap(int* x, int* y);
#define _CRT_SECURE_NO_WARNINGS 1
#include "Heap.h"
// 堆的初始化
void HPInit(HP* php) {
assert(php);
php->arr = NULL;
php->size = php->capacity = 0;
}
// 堆的销毁
void HPDestroy(HP* php) {
assert(php);
if (php->arr) free(php->arr);
php->arr = NULL;
php->capacity = php->size = 0;
}
// 交换
void Swap(int* x, int* y) {
int tmp = *x;
*x = *y;
*y = tmp;
}
// 向上调整
void AdjustUp(HPDataType* arr, int child) {
int parent = (child - 1) / 2;
while (child > 0) {
// >: 大堆
// <: 小堆
if (arr[child] > arr[parent]) {
// 交换
Swap(&arr[child], &arr[parent]);
child = parent;
parent = (child - 1) / 2;
} else {
break;
}
}
}
// 堆的插入数据
void HPPush(HP* php, HPDataType x) {
assert(php);
// 判断空间是否不足
if (php->size == php->capacity) {
int newCapacity = php->capacity == 0 ? 4 : 2 * php->capacity;
// 空间不足需要增容
HPDataType* tmp = (HPDataType*)realloc(php->arr, sizeof(HPDataType) * newCapacity);
if (tmp == NULL) {
perror("realloc fail!");
exit(1);
}
// realloc 成功
php->arr = tmp;
php->capacity = newCapacity;
}
php->arr[php->size] = x;
// 向上调整
AdjustUp(php->arr, php->size - 1);
php->size++;
}
// 向下调整
void AdjustDown(HPDataType* arr, int parent, int n) {
int child = parent * 2 + 1;
while (child < n) {
if (child + 1 < n && arr[child] < arr[child + 1]) {
child++;
}
// > 建小堆
// < 建大堆
if (arr[parent] < arr[child]) {
Swap(&arr[parent], &arr[child]);
parent = child;
child = parent * 2 + 1;
} else {
break;
}
}
}
// 删除堆顶数据
void HPPop(HP* php) {
assert(!HPEmpty(php));
Swap(&php->arr[0], &php->arr[php->size - 1]);
php->size--;
// 向下调整
AdjustDown(php->arr, 0, php->size);
}
// 获取堆顶数据
HPDataType HPTop(HP* php) {
assert(!HPEmpty(php));
return php->arr[0];
}
// 判空
bool HPEmpty(HP* php) {
assert(php);
return php->size == 0;
}
// 求 size
int HPSize(HP* php) {
assert(php);
return php->size;
}
#define _CRT_SECURE_NO_WARNINGS 1
#include "Heap.h"
void test() {
HP hp;
HPInit(&hp);
HPPush(&hp, 1);
HPPush(&hp, 3);
HPPush(&hp, 2);
HPPush(&hp, 4);
/*HPPop(&hp); HPPop(&hp); HPPop(&hp); HPPop(&hp);*/
while (!HPEmpty(&hp)) {
printf("%d ", HPTop(&hp));
HPPop(&hp);
}
HPDestroy(&hp);
}
void test01() {
int arr[] = { 14, 51, 31, 21, 23, 32 };
int n = sizeof(arr) / sizeof(arr[0]);
HP hp;
HPInit(&hp);
// 调用 push 将数组中的数据建堆
for (int i = 0; i < n; i++) {
HPPush(&hp, arr[i]);
}
int i = 0;
while (!HPEmpty(&hp)) {
arr[i++] = HPTop(&hp);
HPPop(&hp);
}
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
HPDestroy(&hp);
}
int main() {
// test();
// test01();
return 0;
}
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。 在线工具，Markdown转HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML转Markdown在线工具，online
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online