顺序结构⼆叉树的实现

如果有⼀个关键码的集合 K = {k0 , k1 , k2 , ...，k(n−1) } ，把它的所有元素按完全⼆叉树的顺序存储⽅式存储，在⼀个⼀维数组中，并满⾜： Ki <= K(2i+1) ( Ki >= K(2i+1) 且 Ki <= K(2i+2 ))，i = 0、1、2... ，则称为⼩堆(或⼤堆)。将根结点最⼤的堆叫做最⼤堆或⼤根堆，根结点最⼩的堆叫做最⼩堆或⼩根堆。

堆的结构

堆的性质

（1）堆中某个结点的值总是不⼤于或不⼩于其⽗结点的值；

（2）堆总是⼀棵完全⼆叉树。

二叉树性质

对于具有 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 否则⽆右孩⼦

在介绍堆的实现之前，我先介绍一个向上调整算法和向下调整算法，因为它涉及到我们堆的实现以及堆排序，也是挺重要的一个知识点，所以我们先看一下这两个算法。

向上调整算法

向上调整算法是关于堆的插入：将新数据插⼊到数组的尾上，再进⾏向上调整算法，直到满⾜堆。

说直白点就是先将元素插⼊到堆的末尾,即最后⼀个孩⼦之后，插⼊之后如果堆的性质遭到破坏，将新插⼊结点顺着其双双亲往上调整到合适位置即可。

接下来就是用代码实现这张图片

//向上调整算法
void AdjustUp(HPDataType* arr, int child)
{
int parent = (child - 1) / 2;
//这里不需要等于，child只要走到根结点的位置，根结点没有父结点不需要交换
while (child > 0)
{
if (arr[child] < arr[parent])
{
Swap(&arr[child], &arr[parent]);
child = parent;
parent = (child - 1) / 2;
}
//插入数据后堆的性质没有改变就可以直接跳出循环
else
{
break;
}
}
}

向下调整算法

向下调整算法是关于堆的删除：删除堆是删除堆顶的数据，将堆顶的数据根最后⼀个数据⼀换，然后删除数组最后⼀个数据，再进⾏向下调整算法。

说直白点就是先将堆顶元素与堆中最后⼀个元素进⾏交换，接着删除堆中最后⼀个元素，最后将堆顶元素向下调整到满⾜堆特性为⽌。

向下调整算法有⼀个前提：左右⼦树必须是⼀个堆，才能调整。

接下来就是用代码实现这张图片

//向下调整算法
void AdjustDown(HPDataType* arr, int parent, int n)
{
int child = (2 * parent) + 1;//左孩子
while (child < n)
{
//先找左右孩子中最小的
if (child + 1 < n && arr[child] > arr[child + 1])
{
child++;
}
if (arr[child] < arr[parent])
{
Swap(&arr[child], &arr[parent]);
parent = child;
child = (2 * parent) + 1;
}
else
{
break;
}
}
}

代码中要判断child+1 < n是因为当arr[child]为数组里最后一个元素，则arr[child+1]会越界。child和child+1是兄弟结点，如果不理解的话可以画一下图。

接下来我们就可以使用这两个算法来完成堆的实现的操作

堆的实现

结构

typedef int HPDataType;
typedef struct Heap {
HPDataType* arr;
int size;
int capacity;
}Heap;

初始化

//堆的初始化
void HeapInit(Heap* php)
{
assert(php);
php->arr = NULL;
php->capacity = php->size = 0;
}

交换

因为入堆和出堆操作都会涉及到两个数之间的交换，我这里就直接创建一个函数来实现两个数之间的交换。

//交换
void Swap(HPDataType* x, HPDataType* y)
{
HPDataType 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 HeapPush(Heap* php, HPDataType x)
{
assert(php);

//检查空间是否足够
if (php->capacity == php->size)
{
int newcapacity = php->capacity == 0 ? 4 : 2 * php->capacity;
HPDataType* tmp = (HPDataType*)realloc(php->arr, sizeof(Heap) * newcapacity);
if (tmp == NULL)
{
perror("realloc fail!");
exit(1);
}
php->arr = tmp;
php->capacity = newcapacity;
}
php->arr[php->size] = x;

//增加完后就要调整堆
AdjustUp(php->arr, php->size);

++php->size;
}

出堆

//向下调整算法
void AdjustDown(HPDataType* arr, int parent, int n)
{
int child = (2 * parent) + 1;
while (child < n)
{
//先判断左子结点和右子结点大小
if (child + 1 < n && arr[child] > arr[child + 1])
{
child++;
}
if (arr[child] < arr[parent])
{
Swap(&arr[child], &arr[parent]);
parent = child;
child = (2 * parent) + 1;
}
else
{
break;
}
}
}

//出堆
void HeapPop(Heap* php)
{
assert(php && php->size);

//出堆出的是堆顶
Swap(&php->arr[0], &php->arr[php->size - 1]);
--php->size;

//出完堆后要向下调整
AdjustDown(php->arr, 0, php->size);
}

取栈顶元素

//取堆顶元素
int HeapTop(Heap* php)
{
assert(php && php->size);
return php->arr[0];
}

判断堆是否为空

//判断堆是否为空
bool HeapEmpty(Heap* php)
{
assert(php);
return php->size == 0;
}

销毁

//堆的销毁
void HeapDestroy(Heap* php)
{
assert(php);
if (php->arr)
free(php->arr);
php->capacity = php->size = 0;
}

堆的实现到这里就结束啦，接下来让我们看看堆的应用有哪些。

堆的应用

堆排序

堆排序意味着数组要排序，我们最容易想到的就是冒泡排序，但是冒泡排序的时间复杂度太差了，所以我们一般都不用冒泡排序解决问题，除非万不得已，另外我们要根据题目的要求来选择用哪个算法解决更好。

方法一

有一种方法就是基于已有数组建堆、取堆顶元素完成排序。接下来看我写的代码尝试去理解这种做法。

void HeapSort(int* arr, int n)
{
    HP hp;
    for(int i = 0; i < n; i++)
    {
    HPPush(&hp,arr[i]);
    }
    int i = 0;
    while (!HPEmpty(&hp))
    {
    arr[i++] = HPTop(&hp);
    HPPop(&hp);
    }
    HPDestroy(&hp);
}

这里我们利用了上面创建好的堆来进行操作，所以它有⼀个前提，就是必须提供有现成的数据结构堆。代码中它是将堆顶的数据覆盖到数组里原有的数据，从而使数组有序。另外这个方法需要我们先创建一个堆再来进行排序，所以这个算法的空间复杂度为O(N)。

方法二

还有一种方法就是：数组建堆，⾸尾交换，交换后的堆尾数据从堆中删掉，将堆顶数据向下调整选出次⼤的数据。

意思就是随便给一个数组，接着直接根据这个数组建堆、排序，而不需要先创建一个堆的数据结构再去取堆顶排序。建堆之前我们先想一下用向上还是向下调整算法建堆好呢？我也不知道用哪个好，那好，我们就来计算一下这两个算法的复杂度分别为多少，再决定使用哪个。

我们先来看向上调整算法建堆

由此可得：向上调整算法建堆时间复杂度为： O(n ∗ log2 n) ( log以2为底， n 为对数)

我们再来看向下调整算法建堆

由此可得：向下调整算法建堆时间复杂度为： O(n)

通过计算两个算法的复杂度并比较，最终我们得出使用向下调整算法建堆更优。其实也不难看出，因为你仔细去看，你会发现

① 在向上调整算法建堆中，结点数量多的层调整次数多 * 结点数量少的层调整次数少

② 在向下调整算法建堆中，结点数量多的层调整次数少 * 结点数量少的层调整次数多

可以看出向上的时间复杂度明显比向下大，所以向下调整算法建堆更优。

下面我就使用向下调整算法建堆去实现堆排序

// 升序，建⼤堆
// 降序，建⼩堆
void HeapSort(int* arr, int n)
{
    // arr数组直接建堆 O(N)
    for (int i = (n-1-1)/2; i >= 0; --i)
    {
   AdjustDown(arr, n, i);
    }
    int end = n - 1;
    while (end > 0)
    {
        Swap(&arr[0], &arr[end]);
        AdjustDown(arr, end, 0);
        --end;
    }
}

以上就是堆排序，下面我们再来分析一下堆排序的时间复杂度。

通过分析发现，堆排序第⼆个循环中的向下调整与建堆中的向上调整算法时间复杂度计算⼀致，此处不再赘述。

因此，堆排序的时间复杂度为 O(n + n ∗ log n) ，即 O(n log n)

Top-K问题

问题描述：即求数据结合中前K个最⼤的元素或者最⼩的元素，⼀般情况下数据量都⽐较⼤。⽐如：专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。

对于Top-K问题，能想到的最简单直接的⽅式就是排序，但是：如果数据量⾮常⼤，排序就不太可取了(可能数据都不能⼀下⼦全部加载到内存中)。最佳的⽅式就是⽤堆来解决，基本思路如下：

（1）⽤数据集合中前K个元素来建堆

① 前k个最⼤的元素，则建⼩堆

② 前k个最⼩的元素，则建⼤堆

（2）⽤剩余的N-K个元素依次与堆顶元素来⽐较，不满⾜则替换堆顶元素

将剩余N-K个元素依次与堆顶元素⽐完之后，堆中剩余的K个元素就是所求的前K个最⼩或者最⼤的元素

接下来就直接通过图片敲代码

void CreatData()
{
//造数据
int n = 100000;
srand(time(0)); 
const char* file = "data.txt";
FILE* fin = fopen(file, "w");
if (fin == NULL)
{
perror("fopen fail");
exit(1);
}
for (int i = 0; i < n; i++)
{
int j = (rand() + i) % 1000000;
fprintf(fin, "%d\n", j);
}

fclose(fin);
}

void Topktest01()
{
int k = 0;
scanf("%d", &k);

const char* file = "data.txt";
FILE* fout = fopen(file, "r");
if (fout == NULL)
{
perror("fopen fail");
exit(2);
}
int* minheap = (int*)malloc(k * sizeof(int));
if (minheap == NULL)
{
perror("malloc fail");
exit(3);
}
//读取文件中前k个数据
for (int i = 0; i < k; i++)
{
fscanf(fout, "%d", &minheap[i]);
}
//建K个数据的小堆
for (int i = (k - 1 - 1) / 2; i >= 0; i--)
{
Adjustdown(minheap, i, k);
}
int x = 0;
while (fscanf(fout, "%d", &x) != EOF)
{
//读取剩余数据，比堆顶的值大，就替换它进堆
if (x > minheap[0])
{
minheap[0] = x;
Adjustdown(minheap, 0, k);
}
}
for (int i = 0; i < k; i++)
{
printf("%d ", minheap[i]);
}

fclose(fout);
}

int main()
{
//先创建一个文件，然后往里面放数据
CreatData();
Topktest01();

return 0;
}

代码中涉及到time所以我们要包含time.h文件，以及涉及到文件操作，如果大家不太熟悉要去回顾一下这方面的内容，还有我这里就没有重复去写向下调整算法函数，如果忘记的话可以看一下上面。

我再解释一下代码的意思，第一步，我先创建了一个文件，名为Data.txt，接着我往里面放入了10万个随机数（为了让大家更直观的感受，我把文件中的前五个数的值扩大成千万位数，使这五个数为所有数里最大的前五个，改完后点击保存）然后我取前K个大的数据分别打印出来，就得到了前五个最大的数，并且它们是以小根堆的形式排序。

顺序结构二叉树的实现到这里就结束啦，本篇内容蛮多的，大家慢慢消化，希望这些内容对大家有所帮助！下篇文章见，希望大家多多来支持一下！

原文地址：https://blog.csdn.net/2402_84433929/article/details/144105638

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：ChatGPT/AI辅助网络安全运营之-数据解压缩
下一篇：Scala习题

Hello World C#
表示这个类只能在同一个程序集内访问。internal可以不要。方法是C#程序的入口点。程序执行时，将从这个方法开始执行。定义了一个叫练习的命名空间。表示这个方法属于类本身，而不是类的实例。定义了一个叫
阅读更多2024-11-30
.cc扩展名是什么语言?主流编程语言扩展名?C语言必须用.c为扩展名吗？为什么看到Windows好多系统文件名的扩展名不超过3字符?
cc是C++语言使用的扩展名，一种说法是它是c with class的简写，当然C++语言使用的扩展名不止.cc和.cpp, 还包含.cxx, .c++, .C等，这些在不同编译器系统采用的默认设定不
阅读更多2024-11-30
Data Guard 三种保护模式介绍
Data Guard 三种保护模式介绍
阅读更多2024-11-30
springboot332基于springboot养老院管理系统pf(论文+源码)_kaic
毕业设计（论文）养老院管理系统设计与实现摘要传统办法管理信息首先需要花费的时间比较多，其次数据出错率比较高，而且对错误的数据进行更改也比较困难，最后，检索数据费事费力。因此，在
阅读更多2024-11-30
react后台管理系统(一)
????个人主页：前端青山 ????系列专栏：React篇 ????人终将被年少不可得之物困其一生依旧青山,本期给大家带来React篇专栏内容:react后台管理系统(一)前言本文档详细介绍了如何从零
阅读更多2024-11-30
Unity类银河战士恶魔城学习总结（P149 Screen Fade淡入淡出菜单）
游戏菜单和死亡动画的淡入淡出
阅读更多2024-11-30
如何查看ubuntu服务器的ssh服务是否可用
默认情况下，SSH 服务监听端口 22。以上方法应该能帮助你确认 SSH 服务是否可用。如果连接成功，表示 SSH 服务是可用的。
阅读更多2024-11-30
软件工程——期末复习（适用于sdut）
虽然在理论上，有些问题可以有最优解，但在实际的软件工程中，所谓的“最好”解决方案通常是相对的，它依赖于具体的项目需求、资源、时间限制、团队技术能力等多重因素。依赖于编程机制可能导致设计的局限性，影响系
阅读更多2024-11-30
Qt creator设置程序图标
Qt 只能使用.ico图片设置为程序图标，若是其他图片，需转换为.ico.
阅读更多2024-11-30
QT知识整理
Moc支持两次清理，第一次清理通常用于移除不需要的C++代码，第二次清理用于移除第一次清理后仍然存在的未使用的代码。：Moc可以将源文件中的资源文件（如图像、字符串等）转换为C++类和函数，使得这些资
阅读更多2024-11-30