【数据结构】二叉树的顺序存储、堆的实现及其应用：堆排序与Top-K问题

请添加图片描述

二叉树的顺序存储、堆的实现及其应用：堆排序与Top-K问题

✨前言：在上一节【树与二叉树】中，我们已经了解了二叉树的基本结构与存储方式。
本篇文章将更进一步，重点介绍 二叉树的顺序结构，并在此基础上引出一个重要的数据结构——堆。
堆作为一种特殊的完全二叉树，在很多场景中都有着广泛应用，例如 堆排序 与 Top-K问题。这两者不仅是数据结构课程的经典内容，也是实际工程中经常遇到的高频问题（如排行榜、搜索结果推荐、日志数据统计等）。
通过本篇文章，你将从堆的概念入手，逐步掌握堆的构建、插入、删除、调整等作，并学会如何利用堆来实现排序和解决Top-K问题。
📖专栏：数据结构与算法

目录

  • 二叉树的顺序存储、堆的实现及其应用：堆排序与Top-K问题
    • 一、二叉树的顺序结构
    • 二、堆的概念及结构
    • 三、堆的实现
      • 3.1 堆的一些简单操作
      • 3.2 堆的插入（堆向上调整算法）
      • 3.3 堆向下调整算法
      • 3.4 堆的删除
      • 3.5 堆的创建
    • 四、堆的应用
      • 4.1 堆排序
        • 堆排序的时间复杂度证明
      • 4.2 TOP-K问题
        • 1. 直接排序法
        • 2. 堆排序思想（推荐）
          • 基本思路：
          • 复杂度分析：
    • 五、总结

一、二叉树的顺序结构

普通的二叉树是不适合用数组来存储的，因为可能会存在大量的空间浪费。而完全二叉树更适合使用顺序结构存储。现实中我们通常把堆(一种二叉树)使用顺序结构的数组来存储，需要注意的是这里的堆和操作系统虚拟进程地址空间中的堆是两回事，一个是数据结构，一个是操作系统中管理内存的一块区域分段。

在这里插入图片描述

二、堆的概念及结构

如果有一个关键码的集合K = { ， ， ，…， }，把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中，并满足： <= 且 <= ( >= 且 >= ) i = 0，1，2…，则称为小堆(或大堆)。将根结点最大的堆叫做最大堆或大根堆，根结点最小的堆叫做最小堆或小根堆。
如下图:

在这里插入图片描述
在这里插入图片描述
由此我们可以得到，堆的性质：
1. 堆中某个结点的值总是不大于或不小于其父结点的值；
2. 堆总是一棵完全二叉树。

三、堆的实现

3.1 堆的一些简单操作

堆的结构定义：

typedef int HPDataType; 
typedef struct Heap
{HPDataType* _a;int _size;int _capacity;
}Heap;

堆的初始化

void HeapInit(Heap* hp) {assert(hp);hp->_a = NULL;hp->_size = 0;hp->_capacity = 0;
}

堆的销毁

void HeapDestroy(Heap* hp) {assert(hp);free(hp->_a);hp->_a = NULL;hp->_size = hp->_capacity = 0;
}

检查并扩容

void HeapCheckCapacity(Heap* hp) {assert(hp);if (hp->_size == hp->_capacity) {int newCapacity = hp->_capacity == 0 ? 4 : hp->_capacity * 2;HPDataType* tmp = (HPDataType*)realloc(hp->_a, newCapacity * sizeof(HPDataType));if (tmp == NULL) {perror("realloc fail");exit(-1);}hp->_a = tmp;hp->_capacity = newCapacity;}
}

获取堆顶元素

HPDataType HeapTop(Heap* hp) 
{assert(hp);assert(!HeapEmpty(hp));return hp->_a[0];
}

获取堆的大小

int HeapSize(Heap* hp) 
{assert(hp);return hp->_size;
}

判断堆是否为空

bool HeapEmpty(Heap* hp) 
{assert(hp);return hp->_size == 0;
}

3.2 堆的插入（堆向上调整算法）

我们先来看一下如何在堆中插入数据（以小堆为例）：

在这里插入图片描述
下面我们就要用新插入节点双亲节点进行比较，如果小于双亲结点，就与双亲节点交换，之后继续与此时的双亲节点比较进行比较，停止条件也很简单，一种就是双亲节点小于新插入的节点，一种就是新插入节点已经是根节点了。
来看一下调整过程：
在这里插入图片描述

调整思想说完了，总结来说，就是，插入数据之后，与其双亲结点比较，然后调整，使其保证堆的性质
下面我们来进行代码的完成：

void Swap(int* x, int* y)
{int tmp = *x; *x = *y;*y = tmp;
}
//向上调整算法
void AdjustUp(int* a, int n)//需要调整的是最后一个
{int child = n - 1;while (child > 0)//新插入的点成为根节点后就不用比较{int parents = (child - 1) / 2;if (a[child] < a[parents]){Swap(&a[child], &a[parents]);child = parents;//新插入的点来到双亲结点}elsebreak;}
}

这种方法也称为堆向上调整算法。
下面我们对于堆的插入代码进行完成：

void HeapPush(Heap* hp, HPDataType x) {assert(hp);// 1. 检查容量HeapCheckCapacity(hp);// 2. 将新元素插入到堆的末尾hp->_a[hp->_size] = x;hp->_size++;// 3. 对最后一个元素进行向上调整，保持堆结构AdjustUp(hp->_a, hp->_size - 1);
}

3.3 堆向下调整算法

现在我们给出一个数组，逻辑上看做一颗完全二叉树。我们通过从根结点开始的向下调整算法可以把它调整成一个小堆。向下调整算法有一个前提：左右子树必须是一个堆，才能调整。

int arr[] = {27,15,19,18,28,34,65,49,25,37};

在这里插入图片描述

下面我们进行代码的完成：

//向下调整算法 
// a: 堆数组
// n: 堆的大小（数组有效长度）
// root: 需要调整的节点的下标（从这个节点开始向下调整）
void AdjustDown(int* a, int n, int root)
{int parent = root;int child = parent * 2 + 1; // 默认先指向左孩子// 当孩子索引还在堆数组范围内时，继续调整while (child < n){// 1. 选出左右孩子中较小的那一个// 如果右孩子存在，且右孩子比左孩子小，则让child指向右孩子if (child + 1 < n && a[child + 1] < a[child]){child++;}// 2. 比较双亲节点和较小的孩子if (a[child] < a[parent]){// 如果孩子比双亲小，则交换它们的内容Swap(&a[child], &a[parent]);// 继续向下调整：双亲指针下沉到孩子的位置parent = child;// 计算新的左孩子位置child = parent * 2 + 1;}else{// 如果双亲已经比两个孩子都小了，说明调整完成，满足堆的性质break;}}
}

有这个算法，我们可以试着对堆顶进行删除

3.4 堆的删除

删除堆是删除堆顶的数据，将堆顶的数据根最后一个数据一换，然后删除数组最后一个数据，再进行向下调整算法。
在这里插入图片描述

// 堆的删除（删除堆顶元素）
void HeapPop(Heap* hp) {assert(hp);assert(!HeapEmpty(hp)); // 堆不能为空// 1. 将堆顶元素与最后一个元素交换Swap(&hp->_a[0], &hp->_a[hp->_size - 1]);// 2. 删除最后一个元素（也就是原来的堆顶）hp->_size--;// 3. 对新的堆顶元素进行向下调整，保持堆结构AdjustDown(hp->_a, hp->_size, 0);
}

3.5 堆的创建

对于堆的创建，我们也要用到堆向下调整算法。

结合堆向下调整算法在这里插入图片描述
那现在就转到了如何找第一个非叶子结点，由于它是完全二叉树，所以它的第一个非叶子结点是它最后一个叶子结点的双亲结点。
最后一个叶子结点：（n-1），则双亲结点为：((n-1-1)/2 )，对于这一点的证明见【树与二叉树：结构、性质与存储】**

// 堆的构建
void HeapCreate(Heap* hp, HPDataType* a, int n) 
{assert(hp && a);assert(n >= 0);// 1. 使用已有的初始化函数HeapInit(hp);if (n == 0) {return;}HeapCheckCapacity(hp); // 2. 拷贝数据memcpy(hp->_a, a, n * sizeof(HPDataType));hp->_size = n;// 3. 构建堆：从最后一个非叶子节点开始向下调整// 最后一个非叶子节点的索引 = (n-1-1)/2 = (n-2)/2for (int i = (n - 1 - 1) / 2; i >= 0; i--) {AdjustDown(hp->_a, n, i);}
}

四、堆的应用

在对上面的内容有了深入了解后，我们可以来看看堆排序和TOP-K问题。

4.1 堆排序

对于排序想必大家应该很熟悉了，就是将无序的一组数据调整为有序，那什么是堆排序呢，就是利用堆的思想进行排序。
那么，现在给出一个数组，如何来排序呢？

int a[] = {1,5,3,8,7,6};

在对于堆的创建和堆的删除有了了解后，我们以升序为例来分析一下，如果我们建一个大堆，然后将堆顶与最后一个数据交换，然后又把除了最后一个数据（原来堆顶的元素，即数组中最大的元素）又重新建堆（和堆的删除思想相似，只是这里我们没有真正删除，而是看做删除了），依次进行上述操作，直到数组中的元素看起来是一个。

总结：

堆排序即利用堆的思想来进行排序，总共分为两个步骤：

  1. 建堆
    升序：建大堆
    降序：建小堆
  2. 利用堆删除思想来进行排序
    建堆和堆删除中都用到了向下调整，因此掌握了向下调整，就可以完成堆排序。

说明一个误区：
在堆排序建堆的时候，我们可能想着直接把数据传入到堆中，然后进行建堆，如下图所示：

在这里插入图片描述
但是，我们真的要这么做吗，其实我们会发现，最终在堆中调整数据还是在数组中进行向下调整算法进行建堆，所以，我们可以不用在堆中的数组中进行建堆，我们直接在原来的数组中不就行了嘛，这一点要清楚，即活学活用。

根据上述总结的步骤我们来完成代码：

void HeapSort(int* a, int n)
{//建堆for (int i = (n - 2) / 2; i >= 0; i--){AdjustDown(a, n, i);}//排序for (int i = n - 1; i > 0; i--){Swap(&a[0], &a[i]);//首尾交换AdjustDown(a, i , 0);//对剩余的进行调整，即对未排序的进行调整}
}

代码写起来很简单，我们来简单的测试一下
在这里插入图片描述

堆排序的时间复杂度证明

没问题。接下来我们来看看堆排序的时间复杂度吧，先说结论：N*logN,再证明：

对于时间复杂度，我们不能盲目的数循环的次数，而是要进行深入的分析：
在这里插入图片描述
因为堆是完全二叉树，而满二叉树也是完全二叉树，此处为了简化使用满二叉树来证明(时间复杂度本来看的就是近似值，多几个结点不影响最终结果)：

  1. 建堆（统一为最坏情况）
    在这里插入图片描述
  2. 排序
    在这里插入图片描述
    我们来详细的推一推这个结果
    在这里插入图片描述
    所以可知，堆排序的时间复杂度为O(N*logN)

辨析：有些人想着为什么不用向上调整算法建堆，一个一个的插入建堆。
这里我们简单提一下：

在这里插入图片描述
可见，它与堆排序的时间复杂度相同，只是一个向下，一个向上调整，所以就没有用的必要了，浪费时间。

4.2 TOP-K问题

TOP-K问题：即求数据结合中前K个最大的元素或者最小的元素，一般情况下数据量都比较大。
比如：专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。
对于Top-K问题，能想到的最简单直接的方式就是排序

1. 直接排序法

最直观的办法是对整个数据集进行排序，然后取前K个元素。

  • 优点：思路简单，容易实现。
  • 缺点：当数据量非常大时，排序的时间复杂度为 O(N log N)，而我们只关心前K个元素，代价太高；另外，数据集可能无法一次性加载进内存，排序难以完成。
2. 堆排序思想（推荐）

最常见、最优的方式是使用 堆（Heap） 来解决。

基本思路：

  • 如果要找 前K大元素：

    • 建立一个小根堆（堆顶是最小值）。

    • 将前K个元素放入堆中。

    • 从第K+1个元素开始，依次与堆顶比较：

      • 如果比堆顶大，就替换堆顶并调整堆；
      • 如果比堆顶小或相等，则忽略。

    • 最终，堆中保留的就是前K大的元素，堆顶即是第K大元素。

代码实现：(因为数据较多，所以我们从文件数据中读取 10000 个整数，利用小根堆的方法，找出前k个最大的数，并打印出来。)

void PrintTopK(int k)
{int* a = (int*)malloc(k * sizeof(int));if (a == NULL)return;FILE* pf = fopen("data.txt", "r");if (pf == NULL) {perror("opening file");return;}for (int i = 0; i < k; i++){fscanf(pf, "%d", &a[i]);}	//建堆for (int i = (k - 2) / 2; i >= 0; i--){AdjustDown(a, i, k);}//调整int x = 0;for (int i = k; i < 10000; i++){fscanf(pf, "%d", &x);if (x > a[0]){a[0] = x;AdjustDown(a, 0, k);}}//打印//注意：这里打印的结果不是有序的，因为堆只保证堆顶最小，并不保证整体有序。for (int i = 0; i < k; i++){printf("%d ", a[i]);}
}

  • 如果要找 前K小元素：

    • 建立一个大根堆（堆顶是最大值），思路类似。
复杂度分析：
  • 建堆时间：O(K)；
  • 扫描剩余 N-K 个元素，每次调整堆的代价为 O(log K)；
  • 总复杂度：O(N log K)，当 K ≪ N 时效率远高于全量排序。
  • 空间复杂度：O(K)。

五、总结

本文首先介绍了二叉树的顺序结构，接着引出了堆这种基于完全二叉树的存储方式，并详细实现了堆的基本操作。在此基础上，我们重点讲解了堆的两个经典应用：堆排序 和 Top-K问题。
通过这些内容我们可以发现，堆的核心思想就是利用完全二叉树的有序性来高效管理数据。无论是排序还是大数据场景下的前K问题，堆都提供了一种比“全量排序”更高效、更节省空间的解决方案。
掌握堆的使用，不仅能加深你对二叉树及排序算法的理解，也能为后续学习优先队列、图算法（如Dijkstra最短路径）、大数据处理等打下坚实基础。

如果本文对您有启发：
✅ 点赞 - 让更多人看到这篇硬核技术解析 ！
✅ 收藏 - 实战代码随时复现
✅ 关注 - 获取数据结构系列深度更新
您的每一个[三连]都是我们持续创作的动力！✨

请添加图片描述

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.mfbz.cn/a/2831.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

SpringBoot 快速上手：从环境搭建到 HelloWorld 实战

SpringBoot 快速上手：从环境搭建到 HelloWorld 实战

在 Java 开发领域&#xff0c;Spring 框架占据着举足轻重的地位&#xff0c;但它复杂的配置曾让不少开发者望而却步。SpringBoot 的出现&#xff0c;如同为 Spring 框架装上了 “加速器”&#xff0c;以 “约定大于配置” 的理念简化了开发流程。本文将从环境准备、Maven 配置入…
阅读更多...
一键部署开源 Coze Studio

一键部署开源 Coze Studio

文章目录一、简介1、什么是 Coze Studio2、参考地址二、安装部署1、安装docker2、安装git3、下载core4、配置公网可用5、登录成功一、简介 1、什么是 Coze Studio Coze Studio 是一站式 AI Agent 开发工具。提供各类最新大模型和工具、多种开发模式和框架&#xff0c;从开发到…
阅读更多...
墨刀原型设计工具操作使用指南及实践操作

墨刀原型设计工具操作使用指南及实践操作

壹、墨刀原型设计工具操作使用指南 一、基础入门 1. 软件版本与环境要求 版本区别&#xff1a; 免费版&#xff1a;支持 3 个项目&#xff0c;单项目最多 20 页&#xff0c;基础组件与交互&#xff0c;团队成员≤5 人&#xff1b;专业版&#xff08;付费&#xff09;&#x…
阅读更多...
博士招生 | 美国圣地亚哥州立大学 Yifan Zhang 课题组博士招生，AI 安全领域顶尖平台等你加入！

博士招生 | 美国圣地亚哥州立大学 Yifan Zhang 课题组博士招生，AI 安全领域顶尖平台等你加入！

内容源自“图灵学术博研社”gongzhonghao学校简介圣地亚哥州立大学&#xff08;San Diego State University, SDSU&#xff09;是美国加州南部久负盛名的公立研究型大学。学校坐落于科技产业高度活跃的南加州地区&#xff0c;与本地软件、电信、生物科技、国防及清洁能源等领域…
阅读更多...
用vscode使用git工具

用vscode使用git工具

基础用法步骤一&#xff1a;打开vscode的git可视化工具步骤二&#xff1a;点击初始化仓库步骤三&#xff1a;选择要加入缓存区的文件注意&#xff1a;这里你可以选择自己想要的文件进行添加。如果想取消缓存区的文件&#xff0c;这里也可以进行取消提交。步骤四&#xff1a;提交…
阅读更多...
portswigger labs XXE漏洞利用实战

portswigger labs XXE漏洞利用实战

lab1 利用外部实体注入获取文件解决此 lab 需要读取到/etc/passwd<!DOCTYPE test [ <!ENTITY cmd SYSTEM "file:///etc/passwd"> ]> <productId>&cmd;</productId>lab2 利用 XXE 执行 SSRF 攻击通过构造 xxe 请求特定的 url 获取目录拼接…
阅读更多...
MySQL表的操作

MySQL表的操作

1.创建表创建表的语法操作&#xff1a;CREATE TABLE table_name (field1 datatype,field2 datatype,field3 datatype) character set 字符集 collate 校验规则 engine 存储引擎;说明&#xff1a;field 表示列名datatype 表示列的数据类型character set 指定字符集&#xff0c;若…
阅读更多...
第2章 cmd命令基础：证书操作（certutil）

第2章 cmd命令基础：证书操作（certutil）

Hi~ 我是李小咖&#xff0c;主要从事网络安全技术开发和研究。 本文取自《李小咖网安技术库》&#xff0c;欢迎一起交流学习&#x1fae1;&#xff1a;https://imbyter.com Certutil是一个Windows操作系统自带的命令行工具&#xff0c;主要用于执行各种与数字证书相关的任务&am…
阅读更多...
LeetCode100-53最大子数组和

LeetCode100-53最大子数组和

本文基于各个大佬的文章 上点关注下点赞&#xff0c;明天一定更灿烂&#xff01; 前言 Python基础好像会了又好像没会&#xff0c;所有我直接开始刷leetcode一边抄样例代码一边学习吧。本系列文章用来记录学习中的思考&#xff0c;写给自己看的&#xff0c;也欢迎大家在评论区指…
阅读更多...
当我们想用GPU（nlp模型篇）

当我们想用GPU（nlp模型篇）

在个人设备上“把 GPU 真正用起来”做 NLP&#xff0c;分五步&#xff1a;准备 → 安装 → 验证 → 训练/推理 → 踩坑排查。下面每一步都给出可复制命令和常见错误。 ────────────────── 1. 硬件准备 • 一张 NVIDIA GPU&#xff0c;算力 ≥ 6.1&#xff08…
阅读更多...
celery

celery

celery是什么celery是Python开发的简单的、灵活可靠的、处理大量消息的分布式任务调度模块专注于实时处理的异步任务队列同时支持任务调度celery本身不含消息服务&#xff0c;它使用第三方消息服务来传递任务&#xff0c;支持的消息服务有RabbitMQ、Redis、Amazon SQS,celery本…
阅读更多...
MeterSphere接口自动化多场景批量运行复制引用

MeterSphere接口自动化多场景批量运行复制引用

一、场景批量执行 全选&#xff0c;点击任意对号后面的三个冒号图标&#xff0c;可以看到批量处理(批量执行、批量编辑、批量移动、批量复制等)批量编辑&#xff0c;可以对用例等级&#xff0c;状态&#xff0c;责任人&#xff0c;运行环境、标签更改 选择批量更改标签&#xf…
阅读更多...
最新文章

Copyright @ 2022~2023