数据结构-堆(带图)详解

前言

本篇博客我们来仔细说一下二叉树顺序存储的堆的结构，我们来看看堆到底如何实现，以及所谓的堆排序到底是什么

💓 个人主页：普通young man-CSDN博客

⏩ 文章专栏：数据结构_普通young man的博客-CSDN博客

      若有问题 评论区见📝

🎉欢迎大家点赞👍收藏⭐文章

目录

树的概念

二叉树的概念及结构

二叉树的基本定义：

二叉树的性质：

特殊的二叉树类型：

存储结构：

操作与遍历：

堆

堆的实现

堆实现的接口

Heap_Init-初始化

IF_Add_capacity-扩容

Swap-数据交换

Heap_Push-插入

Upward-向上调整

​编辑

Heap_Pop-删除

Downward-向下调整

​编辑

Heap_Empty-判空

Heap_Top-获取堆顶数据

Heap_Destory-销毁

堆排序

函数部分

Heap_qsort

top-k问题

Top-K问题的基本概念

解决Top-K问题的常见方法

应用实例

问题

---

树的概念

在学习堆这个数据结构的时候我们先来了解一下什么是树？

树是一种重要的非线性数据结构，它模拟了自然界中树木的结构，不过在计算机科学中，树是倒置的，即根在上，叶在下。树主要由节点（或称为结点）和边组成，用于表示具有层次关系的数据集合。

注意：树的结构子树之间没有交际，否则就不成立

1. 定义：

   • 树是由一个或多个节点组成的有限集合。如果树为空，称为空树；如果不为空，则满足以下条件：
     • 有且仅有一个称为根（root）的节点，它没有前驱节点（即父节点）。
     • 除根节点外，其余每个节点有且仅有一个父节点。
     • 节点的子节点之间没有顺序关系，但每个子节点都可视为一个子树。
     • 树中的节点数可以是任意有限个，包括0（空树）。

2. 节点的度：

   • 一个节点的度是指它拥有子节点的数量。叶子节点（或终端节点）是度为0的节点，即没有子节点的节点。

3. 树的度：

   • 树的度是树中所有节点的度中的最大值。

4. 层次与高度：

   • 节点的层次是从根节点到该节点路径上的边数。根节点的层次为1。
   • 树的高度（或深度）是树中所有节点的层次中的最大值，也就是从根到最远叶子节点的边数。

5. 祖先与后代：

   • 对于非根节点，从该节点到根节点路径上的所有节点（包括根节点）都是该节点的祖先。
   • 一个节点的后代包括它所有的子节点、子节点的子节点等，直至叶子节点。

6. 兄弟节点：

   • 具有相同父节点的节点互为兄弟。

7. 子树：

   • 任何节点及其所有后代节点构成的树称为该节点的子树。

二叉树的概念及结构

接下来我们介绍树中的一种结构二叉树

二叉树是一种特殊的树形数据结构，其中每个节点最多只有两个子节点，通常被称作左子节点和右子节点。这种结构使得二叉树成为计算机科学中研究和应用非常广泛的数据结构之一。下面是关于二叉树的一些核心概念和结构特征：

二叉树的基本定义：

1. 节点：二叉树的基本组成单位，每个节点可以包含一个数据元素以及指向其左右子节点的引用。
2. 根节点：树的顶端节点，没有父节点。
3. 叶子节点：没有子节点的节点。
4. 度：节点的子节点数量，二叉树中节点的度不超过2。
5. 父子关系与兄弟关系：与一般树相同，每个节点（除了根）有唯一的父节点，同一父节点的子节点互为兄弟。

二叉树的性质：

• 有序性：二叉树的子节点分为左子树和右子树，这给树带来了顺序，区别于无序的多叉树。
• 递归定义：一个空集构成空二叉树，或者由一个根节点加上左右两个互不相交的二叉树（左子树和右子树）组成。

特殊的二叉树类型：

• 满二叉树：所有非叶子节点都有两个子节点，且所有叶子节点都在同一层。
• 完全二叉树：除了最后一层，每一层都是满的，且最后一层的叶子节点都尽可能靠左排列。
• 二叉排序树（BST）：左子树所有节点的值小于根节点的值，右子树所有节点的值大于根节点的值，且左右子树也分别是二叉排序树。

存储结构：

• 顺序存储：对于完全二叉树，可以使用数组来紧凑存储，利用数组索引来体现节点间的父子关系。
• 链式存储：更通用的方法，每个节点包含数据和指向左右子节点的指针，通常使用结构体或类来定义节点结构。

操作与遍历：

• 遍历：访问二叉树中所有节点的过程，有前序遍历、中序遍历、后序遍历和层序遍历等方法。
• 插入与删除：在二叉排序树中，根据节点值的比较进行插入或删除操作，并保持二叉排序树的性质。

二叉树因其结构简单、操作方便，常被用于实现各种高效算法，如查找、排序、图的遍历等。在实际应用中，通过选择特定类型的二叉树（如AVL树、红黑树），可以达到平衡性和高效的查询性能。

现实中的二叉树

现在我们了解二叉树的一个概念，我们接下来进入正题

堆

其实堆我们的堆就是二叉树当中的完全二叉树，现实中我们通常把堆(一种二叉树)使用顺序结构的数组来存储，需要注意的是这里的堆和操作系统虚拟进程地址空间中的堆是两回事，一个是数据结构，一个是操作系统中管理内存的一块区域分段。

堆我们分两种：大堆 和 小堆

大堆：

在大堆中，每个节点的值都大于或等于其子节点的值。换句话说，父节点总是大于（或等于）其孩子节点。堆顶元素（根节点）因此是整个堆中的最大值。

小堆：

与大堆相反，小堆中的每个节点的值都小于或等于其子节点的值。这意味着父节点总是小于（或等于）其孩子节点，堆顶元素（根节点）是整个堆中的最小值。

请看这张图

大家知道我们的数据在内存中是b存储结构的模式(物理存储)，但是二叉树是a的逻辑结构，我们的计算机会通过一种叫映射的方式，将这种逻辑结构映射到物理存储。

可能大家会有疑问为什么不直接用数组，而要用堆这个结构？

数组是一种基础且灵活的数据结构，适合存储和访问连续的数据块，特别是在索引访问和随机访问方面表现优秀。然而，在某些特定场景下，尤其是涉及到动态调整数据顺序、维护数据的某种特定排序状态或高效地获取最大值/最小值时，数组的效率可能不如专门设计的数据结构，比如堆。

堆是一种特殊类型的完全二叉树，它具有以下特点，使其在某些应用场景下比简单的数组更加高效和适用：

1. 维护有序性：

   • 最大堆：每个节点的值都大于或等于其子节点的值，堆顶元素始终是最大值。
   • 最小堆：每个节点的值都小于或等于其子节点的值，堆顶元素始终是最小值。 这种特性使得堆在需要频繁查找最大或最小元素的场景（如优先队列）中极为高效，无需遍历整个数组即可快速获得。

2. 动态调整：

   • 堆支持插入和删除元素的同时能够高效地（通常是O(log n)时间复杂度）重新调整结构以维持其特性，这一点在使用数组时难以直接高效实现。

3. 内存利用率：

   • 实际实现时，堆可以采用数组来存储，虽然逻辑上是树状结构，但实际上占用的是连续内存空间，因此内存使用相对高效。

4. 排序应用：

   • 堆可以作为实现堆排序的基础，这是一种不稳定的排序算法，其优势在于能够提供较好的最坏情况和平均时间复杂度（O(n log n)），并且不需要像快速排序那样依赖于数据的初始分布。

堆的实现

先看一下堆的结构咋写，其实和顺序表的结构一样，因为堆本身就是数组，只是逻辑看起不是。

//堆的结构
typedef int HeapTypeData;
typedef struct heap
{HeapTypeData* a;int top;int capacity;
}heap;

记住这张图

堆实现的接口

//初始化
void Heap_Init(heap* obj);
//插入
void Heap_Push(heap* obj, HeapTypeData x);
//删除
void Heap_Pop(heap* obj); 
//判空
bool Heap_Empty(heap* obj);
//获取堆顶
HeapTypeData Heap_Top(heap* obj);
//销毁
void Heap_Destory(heap* obj);
//扩容
void IF_Add_capacity(heap* obj);
//向上调整
void Downward(HeapTypeData* p, int n, int parent);
//向下调整
void Upward(HeapTypeData* p, int child);
//交换
void Swap(HeapTypeData* p1, HeapTypeData* p2);

这些接口是如何实现的嘞？，如何才能创建这么一棵树？

这些接口我会讲解一些没见过德接口，因为这个堆的接口和顺序表差不多

Heap_Init-初始化

//初始化
void Heap_Init(heap* obj) {obj->a = NULL;obj->top = obj->capacity = 0;
}

初始化和顺序表差不多，将指针置NULL，其他的值初始化为0

IF_Add_capacity-扩容

//扩容
void IF_Add_capacity(heap* obj) {if (obj->top == obj->capacity){int new_capeccity = obj->capacity == 0 ? 4 : obj->capacity * 2;HeapTypeData* tmp = (HeapTypeData*)realloc(obj->a,sizeof(HeapTypeData) * new_capeccity);if (tmp == NULL){assert("realloc");}obj->a = tmp;obj->capacity = new_capeccity;}
}

Swap-数据交换

//交换
void Swap(HeapTypeData* p1, HeapTypeData* p2)
{HeapTypeData tmp = *p1;*p1 = *p2;*p2 = tmp;
}

Heap_Push-插入

//插入
void Heap_Push(heap* obj, HeapTypeData x) {assert(obj);IF_Add_capacity(obj);obj->a[obj->top] = x;obj->top++;//这个时候我们需要向上Upward(obj->a,obj->top-1);
}

Upward-向上调整

//向上调整
void Upward(HeapTypeData*p, int child){//通过计算找父母HeapTypeData parent = (child - 1) / 2;while (child > 0){if (p[child] < p[parent]){//交换Swap(&p[child], &p[parent]);//交换后，将parent的位置给给child，继续计算下一个parentchild = parent;parent = (child - 1) / 2;}else{break;}}
}

• eapTypeData *p: 指向堆数组的指针，这个数组存储了堆的所有元素。
• int child: 插入新元素的位置（索引），从0开始计数。新插入的元素被认为是一个“孩子”节点，该函数会检查并调整这个孩子节点与其父节点的关系，以确保堆的性质不变。

函数执行流程：

1. 计算父节点位置：首先根据孩子节点的索引child计算出其父节点的索引parent，公式为(child - 1) / 2。
2. 循环比较并交换：进入一个循环，在循环中不断比较当前孩子节点和其父节点的值。如果孩子节点的值小于父节点的值（对于最小堆而言），则交换这两个节点的值。这是因为最小堆要求父节点的值不大于子节点的值。
3. 更新索引并继续：在交换之后，原来的子节点变成了新的父节点，因此需要更新child为parent，同时基于新的child计算新的parent，继续进行比较和可能的交换，直到孩子节点不再小于其父节点或者到达了堆的根部（即child <= 0时）。
4. 退出循环：一旦发现孩子节点不小于其父节点，或者已经没有父节点可比较（即到达了树的根），循环结束，此时堆的性质已经得到恢复。

Heap_Pop-删除

//删除
void Heap_Pop(heap* obj) {assert(obj);assert(obj->a);assert(obj->top > 0);//先交换，如果直接删除堆顶的数据，就会导致血脉混乱Swap(&obj->a[0], &obj->a[obj->top - 1]);//最后--top就删掉最后一个数据obj->top--;//这边要考虑一个问题，我们是小堆，但是我们的最大的数在堆顶，所以这里需要将最大的数向下移动，让次小的数往上补Downward(obj->a,obj->top,0);
}

Downward-向下调整

//向下调整
void Downward(HeapTypeData* p,int n, int parent) {//计算出左儿子int child = parent * 2 + 1;while (child < n){if(child + 1 < n && p[child+1] < p[child]) {//如果右儿子小于左儿子，直接++到右儿子的位置++child;}if ( p[child] < p[parent])//如果child<parent，就交换,要把小的往上走{//这边操作一样，算法不同Swap(&p[child],&p[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}

• HeapTypeData *p: 指向堆数组的指针。
• int n: 堆中有效元素的数量。在调整过程中，只考虑堆的前n个元素。
• int parent: 当前需要调整的父节点在数组中的索引位置。

函数执行流程：

1. 初始化子节点位置：首先计算出当前父节点的左孩子的索引child，公式为parent * 2 + 1。
2. 循环比较并交换：进入循环，只要child的值小于n，表示还有子节点可以比较。
   • 选择较小的子节点：如果右孩子存在（即child + 1 < n）且右孩子的值小于左孩子的值，则将child更新为右孩子的索引，因为我们要找到两个子节点中更小的那个。
   • 比较并交换：如果找到的子节点child的值小于其父节点parent的值，说明违反了最小堆的性质，这时需要交换它们的值，并将当前的child位置作为新的父节点位置继续向下比较。
   • 更新位置：交换后，原child位置已成为新的父节点位置，因此更新parent = child，并基于新的父节点重新计算其左孩子的索引child = parent * 2 + 1，继续循环。
   • 退出条件：如果子节点不小于父节点，或者已经没有更多的子节点可比较（即child >= n），则跳出循环。
3. 结束：循环结束后，堆的性质得到了恢复，即以parent为根的子树满足最小堆的定义。

Heap_Empty-判空

//判空
bool Heap_Empty(heap* obj) {assert(obj);return !obj->top;
}

Heap_Top-获取堆顶数据

//返回堆顶
HeapTypeData Heap_Top(heap* obj) {assert(obj);assert(obj->a);return obj->a[0];
}

Heap_Destory-销毁

//销毁
void Heap_Destory(heap* obj) {if (obj->a){free(obj->a);obj->a = NULL;obj->capacity = obj->top = 0;}
}

堆排序

//堆排序
void Heap_qsort(int *p,int sz) {建堆//for (int i = 1; i < sz; i++)//	Upward(p,i);//}//建堆for (int i = (sz-1-1)/2; i >= 0; i--)//找最后一个不是叶子的节点{Downward(p,sz,i);}//对堆排序int end = sz - 1;while (end > 0){Swap(&p[0],&p[end]);Downward(p,end,0);--end;}
}
int main() {int a[] = {5,8,9,2,1};int sz = sizeof(a) / sizeof(a[0]);//text1();Heap_qsort(a,sz);int n = 3;for (int i = 0; i < n; i++){printf("%d ", a[i]);}return 0;
}

函数部分

Heap_qsort

• 输入参数:

  • int *p: 指向待排序数组的指针。
  • int sz: 数组的大小，即元素数量。

• 过程:

  1. 建堆:
     • 与传统从第一个非叶节点开始构造堆的方法不同，这里采用了从最后一个非叶节点开始逆序遍历至根节点的方式来构建最小堆。这样做的目的是直接通过Downward函数递归调整每个子树为最小堆，最终整个数组构成一个最小堆。计算最后一个非叶节点的索引公式为(sz-1-1)/2，然后从这个索引开始，逐步向前执行Downward操作。
     • (sz-1-1)/2：sz-1->最后一个元素，sz-1-1找到父节点
  2. 堆排序:
     • 首先，将堆顶元素（数组中的最小值）与数组末尾元素交换，确保当前最小值位于正确的位置（即数组末尾）。
     • 然后，因为堆顶元素（现在是数组的末尾元素）已经正确排序，所以缩小堆的有效大小（end -= 1），并在剩下的元素中再次调用Downward函数调整剩余元素为最小堆。这个过程重复，直到整个数组都被正确排序。

• 输出:

  • 数组p的内容将会按照升序排列。

这边我用gif来展示堆排序的逻辑

这边我建的是一个小堆

排序

那这个堆排序的时间复杂度是多少嘞？

那我们就来算一算

得出结论是n*logn

这里面得计算也可以套公式

top-k问题

Top-K问题是一类在大数据集或流式数据中寻找或维护最顶尖（最大或最小）K个元素的问题。这类问题广泛应用于各种场景，特别是在需要高效地处理大量数据并提取关键信息时，比如数据分析、推荐系统、搜索引擎排名、社交网络分析、金融风控、大数据处理等领域。

Top-K问题的基本概念

在最简单的形式中，Top-K问题可以表述为：给定一个包含N个元素的无序集合，找出其中最大的K个元素或最小的K个元素。这里的“最大”或“最小”可以根据具体应用需求定义，比如数值大小、频率、相关性等。

解决Top-K问题的常见方法

1. 快速选择算法：基于快速排序的选择算法变体，通过一次划分过程确定一个基准元素的位置，如果基准元素恰好处于第K个位置，则找到答案；否则，在基准元素的正确一侧递归继续查找。

2. 堆方法：维护一个大小为K的小顶堆（找最大K个元素）或大顶堆（找最小K个元素），遍历数据时，比较堆顶元素与当前元素，如果满足条件则替换堆顶元素并调整堆结构，保证堆的性质。这种方法的时间复杂度接近O(N log K)。

3. 二分查找法：适用于能够计算数组中某个值排名或能够估算某个值排名的场景。通过二分查找确定一个阈值，然后统计小于或大于该阈值的元素个数，逐步逼近目标K值。

4. 桶排序或计数排序：对于数据范围有限且分布均匀的情况，可以将数据分布到有限数量的桶中，然后从桶中找出Top-K元素。适合特定场景下提高效率。

应用实例

1. 搜索引擎：在搜索引擎中，为了提供最相关的网页给用户，搜索引擎会根据页面质量、关键词匹配程度等因素对网页进行评分，然后选择评分最高的K个网页展示给用户。

2. 推荐系统：电商平台或社交媒体平台会根据用户的浏览历史、购买行为、喜好等数据，计算商品或内容的相关性分数，选出评分最高的K个商品或内容推荐给用户。

3. 大数据分析：在处理大规模日志数据时，可能需要找出访问量最大的K个IP地址、最常见的K个错误类型等，以帮助识别异常或优化资源分配。

4. 金融风控：银行和金融机构利用Top-K分析来识别潜在的高风险交易，比如监测账户中交易额最大的K笔交易，以发现可能的洗钱活动。

Top-K问题因其高效性和实用性，在现代信息技术领域扮演着重要角色。

问题

现在你在面试，面试官要你找出10亿得数据中最大得前十个？你该咋找？或许你会说直接用刚才得堆排序，这当然可以。

那假如，面试官让你用1MB的空间去找这个个数中最大十个嘞？

大家或许就有一点懵逼了吧，哈哈哈

看图

于是我们的代码就可以这样写

//实现创建x(整形)个数据的一个文件，利用1MB空间在x数据中找最大的前n个#include<time.h>
//造数据
void Make_data() {int n = 100000;srand((unsigned int)time(NULL));const char* date = "Date.txt";FILE* write = fopen(date,"w");if (write == NULL){assert("fopen");return;}//将数据写入文件for (int i = 0; i < n; i++){int ret =  (rand() + i) % n;//+i == 防止重复值，i是不断变化的，%n == 控制范围fprintf(write,"%d\n",ret);//将生成的数据不断的插入 "Date.txt"文件中}fclose(write);
}//建堆
//数据量大
Make_heap() {int n = 0;printf("请输入你要查看的前几个数");scanf("%d",&n);//创建一个空间int* New_node = (int*)malloc(n*sizeof(int));if (New_node == NULL){assert("malloc");return;}//将数据从文件中读出const char* write = "Date.txt";FILE* read = fopen(write,"r");if (read == NULL){assert("fopen");return;}//先把进n个数据for (int i = 0; i < n; i++){fscanf(read,"%d", &New_node[i]);}//建堆sfor (int i = (n-1-1)/2; i >= 0; i--){Downward(New_node,n,i);}//比较剩下的数据依次int end = 0;while (fscanf(read,"%d",&end) > 0)//这里会返回EOF(-1){//判断if (end > New_node[0]) {//如果end>Newnode[0]位置的数，直接将这个位置的值赋值New_node[0] = end;//再进行向下调整得到小堆Downward(New_node,n,0);}}fclose(read);Heap_qsort_print(New_node,n);
}
Heap_qsort_print(int* p, int n) {//排序：从大到小int new_size = n - 1;while (new_size > 0){Swap(&p[0], &p[new_size]);Downward(p, new_size, 0);--new_size;}//输出printf("最大的%d个数>: ", n);for (int i = 0; i < n; i++){printf("%d ", p[i]);}
}
int main() {//设置时间戳//Make_data();//建堆Make_heap();}

1. 生成数据: Make_data 函数生成100,000个整数数据并存储到一个名为"Date.txt"的文件中。每个数据是通过随机数生成器得到，并加上循环变量i后取模，以避免重复并控制数据范围。

2. 读取并找出Top-N: Make_heap函数首先询问用户想要找出数据文件中的前多少个最大数，然后读取文件内容，使用最小堆（这里实际实现的是一个简化版的维护最大值的过程，未完全实现标准的堆结构）来维护当前找到的最大N个数。它先读取前N个数构建初始“堆”，之后继续读取文件中的剩余数据并与堆顶元素比较，若遇到更大的数则替换堆顶元素并重新调整堆。最后，使用Heap_qsort_print函数对维护的N个数进行排序并打印。

3. 排序及打印: Heap_qsort_print函数实质上是进行了一个非典型的堆排序操作，从堆顶开始每次将堆顶元素（当前最大值）与末尾元素交换，并缩小堆的大小，重复此过程直至整个序列变为降序排列，最后打印出这N个最大的数。

ok今天的博客就结束了哦