C算法
数据结构：二叉树与堆的结构及实现
系统讲解了树与二叉树的基础概念、性质及存储方式，重点阐述了堆（Heap）的数据结构特性与大/小顶堆的实现原理。内容涵盖堆的初始化、插入、删除、上下调整算法，并展示了堆在 Top-K 问题筛选及堆排序中的实际应用。文章采用 C 语言进行代码演示，适合数据结构初学者深入理解。
系统讲解了树与二叉树的基础概念、性质及存储方式，重点阐述了堆（Heap）的数据结构特性与大/小顶堆的实现原理。内容涵盖堆的初始化、插入、删除、上下调整算法，并展示了堆在 Top-K 问题筛选及堆排序中的实际应用。文章采用 C 语言进行代码演示，适合数据结构初学者深入理解。
树是一种非线性的数据结构，它是由 n（n>=0）个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。
有一个特殊的结点，称为根结点，根结点没有前驱结点。 除根结点外，其余结点被分成 M(M>0) 个互不相交的集合 T1、T2、……、Tm，其中每一个集合 Ti(1<= i <= m) 又是一棵结构与树类似的子树。每棵子树的根结点有且只有一个前驱，可以有 0 个或多个后继。 因此，树是递归定义的。
注意：树形结构中，子树之间不能有交集，否则就不是树形结构。
空树高度为 0，只有根节点高度为一。
树结构相对线性表就比较复杂了，要存储表示起来就比较麻烦了。既然保存值域，也要保存结点和结点之间的关系，实际中树有很多种表示方式如：双亲表示法，孩子表示法、孩子双亲表示法以及孩子兄弟表示法等。我们这里就简单的了解其中最常用的孩子兄弟表示法。
typedef int DataType;
struct TreeNode {
struct TreeNode* leftChild; // 第一个孩子结点---左孩子
struct TreeNode* rightBrother; // 指向其下一个兄弟结点-----右兄弟
DataType data; // 结点中的数据域
};
无论一个父亲节点有多少孩子，child 指向左边第一个节点。
树在实际中常用于表示文件系统的目录树结构。
一棵二叉树是结点的一个有限集合，该集合:
从上图可以看出：
注意：对于任意的二叉树都是由以下几种情况复合而成的。
二叉树一般可以使用两种结构存储，一种顺序结构，一种链式结构。
顺序结构存储就是使用数组来存储，一般使用数组只适合表示完全二叉树，因为不是完全二叉树会有空间的浪费。而现实中使用中只有堆才会使用数组来存储。二叉树顺序存储在物理上是一个数组，在逻辑上是一颗二叉树。
二叉树的链式存储结构是指，用链表来表示一棵二叉树，即用链来指示元素的逻辑关系。通常的方法是链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址。链式结构又分为二叉链和三叉链，当前我们学习中一般都是二叉链，后面课程学到高阶数据结构如红黑树等会用到三叉链。
普通的二叉树是不适合用数组来存储的，因为可能会存在大量的空间浪费。而完全二叉树更适合使用顺序结构存储。现实中我们通常把堆 (一种二叉树) 使用顺序结构的数组来存储，需要注意的是这里的堆和操作系统虚拟进程地址空间中的堆是两回事，一个是数据结构，一个是操作系统中管理内存的一块区域分段。
如果有一个关键码的集合 K = { ， ， ，…， }，把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中，并满足： <= 且 <= ( >= 且 >= ) i = 0，1，2…，则称为小堆 (或大堆)。将根结点最大的堆叫做最大堆或大根堆，根结点最小的堆叫做最小堆或小根堆。
堆的性质：
大堆跟小堆都是完全二叉树。
同样使用多文件操作，Heap.h 用来放函数的声明，Heap.c 放函数的实现，test.c 用来测试。
typedef int HPDataType;
typedef struct Heap {
HPDataType* a;
int size;
int capacity;
} HP;
void HPInit(HP* php) {
assert(php);
php->a = NULL;
php->capacity = php->size = 0;
}
void HPDestroy(HP* php) {
assert(php);
free(php->a);
php->a = NULL;
php->capacity = php->size = 0;
}
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 HPPush(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); // 数组下标从 0 开始
}
void AdjustDown(HPDataType* a, int n, int parent) {
// 假设法 先假设左孩子小
int child = parent * 2 + 1;
while (child < n) // child>=n 说明孩子不存在 调整到叶子了 n 是数组大小
{
// 找出小的孩子
if (child + 1 < n && a[child + 1] < a[child]) // 当左孩子取 n-1 时 右孩子 a[n] 越界访问 所有要再加一个判断条件
{
child++; // child+1 变成右孩子
}
if (a[child] < a[parent]) {
Swap(&a[child], &a[parent]);
parent = child;
child = parent * 2 + 1;
} else {
break;
}
}
}
删除堆是删除堆顶的数据，将堆顶的数据根最后一个数据一换，然后删除数组最后一个数据，再进行向下调整算法。
void HPPop(HP* php) {
assert(php);
assert(php->size > 0);
Swap(&php->a[0], &php->a[php->size - 1]);
php->size--;
AdjustDown(php->a, php->size, 0);
}
bool HPEmpty(HP* php) {
assert(php);
return php->size == 0;
}
HPDataType HPTop(HP* php) // 返回堆顶元素
{
assert(php);
assert(php->size > 0);
return php->a[0];
}
给一个数组让他按顺序打印。
#include "Heap.h"
void Test01() {
int a[] = {2, 4, 5, 7, 3, 2, 1, 5};
HP hp;
HPInit(&hp);
for (size_t i = 0; i < sizeof(a) / sizeof(int); i++) {
HPPush(&hp, a[i]); // push 就是建堆 把 a[i] 依次放入
}
while (!HPEmpty(&hp)) {
printf("%d ", HPTop(&hp));
HPPop(&hp);
}
}
int main() {
Test01();
return 0;
}
Heap.h
#pragma once
#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 HPInit(HP* php);
void HPDestroy(HP* php);
void HPPush(HP* php, HPDataType x);
void HPPop(HP* php); // 删除堆顶的数据
void AdjustUp(HPDataType* a, int x);
void AdjustDown(HPDataType* a, int n, int parent);
HPDataType HPTop(HP* php);
bool HPEmpty(HP* php);
Heap.c
#define _CRT_SECURE_NO_WARNINGS
#include "Heap.h"
void Swap(HPDataType* p1, HPDataType* p2) {
HPDataType tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
void HPInit(HP* php) {
assert(php);
php->a = NULL;
php->capacity = php->size = 0;
}
void HPDestroy(HP* php) {
assert(php);
free(php->a);
php->a = NULL;
php->capacity = php->size = 0;
}
void HPPush(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); // 数组下标从 0 开始
}
// 向上调整
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 HPPop(HP* php) {
assert(php);
assert(php->size > 0);
Swap(&php->a[0], &php->a[php->size - 1]);
php->size--;
AdjustDown(php->a, php->size, 0);
}
void AdjustDown(HPDataType* a, int n, int parent) {
// 假设法 先假设左孩子小
int child = parent * 2 + 1;
while (child < n) // child>=n 说明孩子不存在 调整到叶子了 n 是数组大小
{
// 找出小的孩子
if (child + 1 < n && a[child + 1] < a[child]) // 当左孩子取 n-1 时 右孩子 a[n] 越界访问 所有要再加一个判断条件
{
child++; // child+1 变成右孩子
}
if (a[child] < a[parent]) {
Swap(&a[child], &a[parent]);
parent = child;
child = parent * 2 + 1;
} else {
break;
}
}
}
HPDataType HPTop(HP* php) // 返回堆顶元素
{
assert(php);
assert(php->size > 0);
return php->a[0];
}
bool HPEmpty(HP* php) {
assert(php);
return php->size == 0;
}
test.c
#define _CRT_SECURE_NO_WARNINGS
#include "Heap.h"
void Test01() {
int a[] = {2, 4, 5, 7, 3, 2, 1, 5};
HP hp;
HPInit(&hp);
for (size_t i = 0; i < sizeof(a) / sizeof(int); i++) {
HPPush(&hp, a[i]); // push 就是建堆 把 a[i] 依次放入
}
/*while (!HPEmpty(&hp)) { printf("%d", HPTop(&hp)); HPPop(&hp); }*/
int k = 0;
scanf("%d", &k);
while (k--) {
printf("%d ", HPTop(&hp));
HPPop(&hp);
}
}
int main() {
Test01();
return 0;
}
TOP-K 问题：即求数据集合中前 K 个最大的元素或者最小的元素，一般情况下数据量都比较大。 比如：专业前 10 名、世界 500 强、富豪榜、游戏中前 100 的活跃玩家等。 对于 Top-K 问题，能想到的最简单直接的方式就是排序，但是：如果数据量非常大，排序就不太可取了 (可能数据都不能一下子全部加载到内存中)。最佳的方式就是用堆来解决，基本思路如下：
void PrintTopK(int* a, int n, int k) {
// 1. 建堆--用 a 中前 k 个元素建堆
// 2. 将剩余 n-k 个元素依次与堆顶元素交换，不满则则替换
}
void TestTopk() {
int n = 10000;
int* a = (int*)malloc(sizeof(int)*n);
srand(time(0));
for (size_t i = 0; i < n; ++i) {
a[i] = rand() % 1000000;
}
a[5] = 1000000 + 1;
a[1231] = 1000000 + 2;
a[531] = 1000000 + 3;
a[5121] = 1000000 + 4;
a[115] = 1000000 + 5;
a[2335] = 1000000 + 6;
a[9999] = 1000000 + 7;
a[76] = 1000000 + 8;
a[423] = 1000000 + 9;
a[3144] = 1000000 + 10;
PrintTopK(a, n, 10);
}
堆排序即利用堆的思想来进行排序，总共分为两个步骤：
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 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