AI 助理
文档备案控制台
开发者社区 人工智能 文章 正文

二叉树的顺序结构——堆的概念&&实现（图文详解+完整源码 | C语言版）

2023-04-18 273
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 二叉树的顺序结构——堆的概念&&实现（图文详解+完整源码 | C语言版）

目录

0.写在前面

1.什么是堆？

2.堆的实现

2.1 堆的结构定义

2.2 函数声明

2.3 函数实现

2.3.1 AdjustUp（向上调整算法）

2.3.2 AdjustDown（向下调整算法）

2.3.3 HeapCreate（如何建堆）

2.3.4 建堆的时间复杂度

3. 完整源码

Heap.h文件

Heap.c文件

Test.c文件  


写在前面

上一章中介绍了树和二叉树的概念及结构，本章我们将学习堆的实现。


正文

1.什么是堆？


堆是一种完全二叉树。只不过堆是二叉树顺序结构的实现，说白了就是将一个数组看作二叉树。也就是说，堆的逻辑结构是一棵二叉树，存储结构是数组。


堆又分为大堆和小堆：


大堆：树中所有父亲都大于等于孩子；


小堆：树中所有父亲都小于等于孩子。


注意，不满足这两点的二叉树不能称为堆（这点很重要）。

0.png


2.堆的实现


2.1 堆的结构定义


typedef int HPDataType;
typedef struct Heap
{
  HPDataType* a;  //存储数据
  int size;   //堆有效数据的大小
  int capacity; //堆的容量
}Heap;

上文讲到，堆其实就是二叉树的顺序结构实现，所以用一个数组来存储数据。


2.2 函数声明


//给出一个数组，对它进行建堆
void HeapCreate(Heap* php, HPDataType* a, int n);
//堆的初始化
void HeapInit(Heap* php);
//对申请的内存释放
void HeapDestroy(Heap* php);
//添加数据
void HeapPush(Heap* php, HPDataType data);
//删除数据
void HeapPop(Heap* php);
//向上调整算法
void AdjustUp(HPDataType* a, int child);
//向下调整算法
void AdjustDown(HPDataType* a, int n, int parent);
//打印堆的数据
void HeapPrint(Heap* php);
//判断堆是否为空
bool HeapEmpty(Heap* php);
//返回堆的大小
int HeapSize(Heap* php);
//返回堆顶的数据
HPDataType HeapTop(Heap* php);
//交换函数
void Swap(HPDataType* p1, HPDataType* p2);


2.3 函数实现


由于堆的实现所用函数较多，这里就挑其中最难也是最重要的进行说明。


2.3.1 AdjustUp（向上调整算法）


当我们要实现在HeapPush（堆中添加数据data时），我们的做法是先将data插入到堆的尾部，再将data进行向上调整，直到它到达合适的位置。

如图，假设现在要将data=60添加到下面这个大堆中。

1.png

第一步，将60插入到堆的末尾，即数组的末尾。

2.png

第二步，比较60与它父亲节点的大小。因为要保证插入数据之后堆仍然是大堆，所以如果60大于父亲，则交换位置。

3.png

第三步，继续比较60与父亲的值，若大于父亲则交换位置。


4.png

至此，60已经到它正确的位置上了。

以上就是向上调整的过程，来看看代码实现。

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 HeapPush(Heap* php, HPDataType data)
{
  assert(php);
  //如果容量不足就扩容
  if (php->size == php->capacity)
  {
    int newCapacity = php->capacity == 0 ? 4 : php->capacity * 2;
    HPDataType* tmp = (HPDataType*)realloc(php->a, sizeof(HPDataType)*newCapacity);
    if (tmp == NULL)
    {
      perror("realloc fail");
      exit(-1);
    }
    php->a = tmp;
    php->capacity = newCapacity;
  }
  //添加数据
  php->a[php->size] = data;
  php->size++;
  //将新入堆的data进行向上调整
  AdjustUp(php->a, php->size-1);
}


2.3.2 AdjustDown（向下调整算法）


当我们要实现HeapPop（删除堆顶的数据）时，我们不能像往常的数组那样进行头删。因为数组再进行头删时，还要将从第二个位置起的后面的所有元素都向前平移。

但是堆这样行不通，因为随意挪动数据会造成关系的混乱。例如00.png

此时这个二叉树结构就不再是一个大堆了。

那么有什么好的办法不使堆的结构紊乱呢？这就得用到向下调整算法了。

例如，假设此时要删除堆顶的数据：000.png


第一步，交换堆顶与堆尾的值，并将堆的Size--（相当于删除了末尾的元素）。


5.png


第二步，对45进行向下调整。找出45的两个孩子中值最大（是小堆就选小的）的那个，如果5小于该数字就与其进行交换。


6.png


循环此步骤，直至45到达正确的位置。


显然，此时情况较为简单，只用一步就到达了正确位置。（此时70已经不存在了，所以不用比较）


以上就是向下调整的过程，来看看代码的实现。


void AdjustDown(HPDataType* a, int n, int parent)
{
  assert(a);
  //先默认较大的为左孩子
  int child = parent * 2+1;
  while (child<n)
  {
    //如果右孩子比左孩子大，就++
    if (a[child] < a[child + 1] && child + 1 < n)
    {
      child++;
    }
    //建大堆用'>'，小堆用'<'
    if (a[child] > a[parent])
    {
      Swap(&a[child], &a[parent]);
      parent = child;
      child = parent * 2 + 1;
    }
    else
    {
      break;
    }
  }
}
void HeapPop(Heap* php)
{
  assert(php);
  assert(php->size>0);
  //将堆顶的数据与堆尾交换
  Swap(&php->a[0], &php->a[php->size - 1]);
  php->size--;
  //将此时堆顶的data向下调整
  AdjustDown(php->a, php->size, 0);
}

特别注意：不管是向上调整还是向下调整，它们都得满足一个前提->

向上调整：进行向上调整的时候，该位置之前的所有数据已经是一个堆了。

向下调整：进行向下调整的时候，该位置的左子树和右子树都已经是堆了。


2.3.3 HeapCreate（如何建堆）


此函数所实现的功能是给出一个数组，对数组进行建堆（建大堆或者小堆）。

先来看看代码实现：

void HeapCreate(Heap* php, HPDataType* a, int n)
{
  php->a = (HPDataType*)malloc(sizeof(HPDataType) * n);
  if (php->a == NULL)
  {
    perror("malloc fail");
    exit(-1);
  }
  //将数组的内容全部拷贝到php->a中
  memcpy(php->a, a, sizeof(HPDataType) * n);
  php->size = php->capacity = n;
  //建堆算法
  for (int i = (n - 1 - 1) / 2; i >= 0; i--)
  {
    AdjustDown(php->a, n, i);
  }
}

这里采用向下调整算法的的思路是，既然向下调整和向上调整都是有前提的，就不能直接进行使用。但是我们发现即使这个二叉树的数据是紊乱的，但是总有可以当作堆的一部分来使用向下调整（不用向上调整是因为不好控制）。例如：7.png

在这个堆的底部（3个黑色圆圈里的部分）可以看作是堆，可以满足进行向下调整的条件。当把底层的三个堆建好以后，我们发现两个红色圆圈中的部分又可以看作满足条件的堆，对这两部分在进行向下调整。


9.png


完成之后，我们发现堆顶元素的左子树和右子树都已经是堆了，最后再将堆顶的元素进行向下调整，就建好一个完整的堆了。


总结起来就是如下图的步骤：

8.png


2.3.4 建堆的时间复杂度


因为堆是完全二叉树，而满二叉树也是完全二叉树，此处为了简化使用满二叉树来证明(时间复杂度本来看的就是近似值，多几个节点不影响最终结果)：55.png因此，建堆的时间复杂度为O(N)。


3. 完整源码


Heap.h文件


#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<string.h>
#include<stdbool.h>
typedef int HPDataType;
typedef struct Heap
{
  HPDataType* a;   //存储数据
  int size;       //堆有效数据的大小
  int capacity;     //堆的容量
}Heap;
//给出一个数组，对它进行建堆
void HeapCreate(Heap* php, HPDataType* a, int n);
//堆的初始化
void HeapInit(Heap* php);
//对申请的内存释放
void HeapDestroy(Heap* php);
//添加数据
void HeapPush(Heap* php, HPDataType data);
//删除数据
void HeapPop(Heap* php);
//向上调整算法
void AdjustUp(HPDataType* a, int child);
//向下调整算法
void AdjustDown(HPDataType* a, int n, int parent);
//打印堆的数据
void HeapPrint(Heap* php);
//判断堆是否为空
bool HeapEmpty(Heap* php);
//返回堆的大小
int HeapSize(Heap* php);
//返回堆顶的数据
HPDataType HeapTop(Heap* php);
//交换函数
void Swap(HPDataType* p1, HPDataType* p2);


Heap.c文件 


#define _CRT_SECURE_NO_DEPRECATE 1
#include"Heap.h"
void HeapCreate(Heap* php, HPDataType* a, int n)
{
  php->a = (HPDataType*)malloc(sizeof(HPDataType) * n);
  if (php->a == NULL)
  {
    perror("malloc fail");
    exit(-1);
  }
  //将数组的内容全部拷贝到堆中
  memcpy(php->a, a, sizeof(HPDataType) * n);
  php->size = php->capacity = n;
  //建堆算法
  for (int i = (n - 1 - 1) / 2; i >= 0; i--)
  {
    AdjustDown(php->a, n, i);
  }
}
void HeapInit(Heap* php)
{
  assert(php);
  php->a = NULL;
  php->size = php->capacity = 0;
}
void HeapPrint(Heap* php)
{
  assert(php);
  for (int i = 0; i < php->size; i++)
  {
    printf("%d ", php->a[i]);
  }
}
void HeapDestroy(Heap* php)
{
  assert(php);
  free(php->a);
  php->a = NULL;
  php->capacity = php->size = 0;
}
void HeapPush(Heap* php, HPDataType data)
{
  assert(php);
  //如果容量不足就扩容
  if (php->size == php->capacity)
  {
    int newCapacity = php->capacity == 0 ? 4 : php->capacity * 2;
    HPDataType* tmp = (HPDataType*)realloc(php->a, sizeof(HPDataType)*newCapacity);
    if (tmp == NULL)
    {
      perror("realloc fail");
      exit(-1);
    }
    php->a = tmp;
    php->capacity = newCapacity;
  }
  //添加数据
  php->a[php->size] = data;
  php->size++;
  //将新入堆的data进行向上调整
  AdjustUp(php->a, php->size-1);
}
void HeapPop(Heap* php)
{
  assert(php);
  assert(php->size>0);
  //将堆顶的数据与堆尾交换
  Swap(&php->a[0], &php->a[php->size - 1]);
  php->size--;
  //将此时堆顶的data向下调整
  AdjustDown(php->a, php->size, 0);
}
void AdjustDown(HPDataType* a, int n, int parent)
{
  assert(a);
  //先默认较大的为左孩子
  int child = parent * 2+1;
  while (child<n)
  {
    //如果右孩子比左孩子大，就++
    if (a[child] < a[child + 1] && child + 1 < n)
    {
      child++;
    }
    //建大堆用'>'，小堆用'<'
    if (a[child] > a[parent])
    {
      Swap(&a[child], &a[parent]);
      parent = child;
      child = parent * 2 + 1;
    }
    else
    {
      break;
    }
  }
}
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;
    }
  }
}
HPDataType HeapTop(Heap* php)
{
  assert(php);
  assert(php->size>0);
  return php->a[0];
}
int HeapSize(Heap* php)
{
  assert(php);
  return php->size;
}
bool HeapEmpty(Heap* php)
{
  assert(php);
  return !php->size;
}
void Swap(HPDataType* p1, HPDataType* p2)
{
  HPDataType tmp = *(p1);
  *(p1) = *(p2);
  *(p2) = tmp;
}


Test.c文件  


#define _CRT_SECURE_NO_DEPRECATE 1
#include"Heap.h"
void test()
{
  HPDataType arr[10] = { 12,34,45,78,56,74,3,7,9,5 };
  Heap hp;
  HeapCreate(&hp, arr, 10);
  //HeapInit(&hp);
  //HeapPush(&hp, 10);
  //HeapPush(&hp, 70);
  //HeapPush(&hp, 15);
  //HeapPush(&hp, 30);
  //HeapPush(&hp, 25);
  //HeapPrint(&hp);
  //HeapPop(&hp);
  //HeapPrint(&hp);
  //HeapPop(&hp);
  //HeapPrint(&hp);
  //HeapPop(&hp);
  HeapPrint(&hp);
}
int main()
{
  test();
  return 0;
}

至此，本章的内容就结束了，下一章将进行堆的实际应用——堆排序以及TopK问题的说明。


文章标签：
算法
存储
花想云
目录
相关文章
hahaha无
|
存储 C语言
c语言——二叉树
二叉树的概念在这里就不进行过多的赘述，那么主要说一下我认为重要的部分，第一点就是二叉树里面部分概念的理解：就比如说，你对于如何构建二叉树，掌握的十分深刻，但刷题的时候对于一些题目所给的概念不清楚，导致看不明白题目，这课不好，二叉树的概念如下图所示,其实都很简单，主要是当给他的名字时，你明不明白。还有对于满二叉树与完全二叉树。
hahaha无
370 0
RossyYan
|
存储 安全 C语言
【C语言程序设计——选择结构程序设计】预测你的身高（头歌实践教学平台习题）【合集】
分支的语句，这可能不是预期的行为，这种现象被称为“case穿透”，在某些特定情况下可以利用这一特性来简化代码，但在大多数情况下，需要谨慎使用。编写一个程序，该程序需输入个人数据，进而预测其成年后的身高。根据提示，在右侧编辑器补充代码，计算并输出最终预测的身高。分支下的语句，提示用户输入无效。常量的值必须是唯一的，且在同一个。语句的作用至关重要，如果遗漏。开始你的任务吧，祝你成功！，程序将会继续执行下一个。常量都不匹配，就会执行。来确保程序的正确性。
RossyYan
647 10
RossyYan
|
小程序 C语言
【C语言程序设计——基础】顺序结构程序设计（头歌实践教学平台习题）【合集】
目录 任务描述 相关知识 编程要求 测试说明 我的通关代码: 测试结果： 任务描述 相关知识 编程编写一个程序，从键盘输入3个变量的值，例如a=5，b=6，c=7，然后将3个变量的值进行交换，使得a=6，b=7，c=5。面积=sqrt(s(s−a)(s−b)(s−c))，s=(a+b+c)/2。使用输入函数获取半径，格式指示符与数据类型一致，实验一下，不一致会如何。根据提示，在右侧编辑器补充代码，计算并输出圆的周长和面积。
RossyYan
526 10
RossyYan
|
存储 编译器 C语言
【C语言程序设计——选择结构程序设计】求一元二次方程的根（头歌实践教学平台习题）【合集】
本任务要求根据求根公式计算并输出一元二次方程的两个实根，精确到小数点后两位。若方程无实根，则输出提示信息。主要内容包括： - **任务描述**：使用求根公式计算一元二次方程的实根。 - **相关知识**：掌握 `sqrt()` 函数的基本使用方法，判断方程是否有实根。 - **编程要求**：根据输入的系数，计算并输出方程的根或提示无实根。 - **测试说明**：提供两组测试数据及预期输出，确保代码正确性。 - **通关代码**：包含完整的 C 语言代码示例，实现上述功能。 通过本任务，你将学会如何处理一元二次方程的求解问题，并熟悉 `sqrt()` 函数的使用。
RossyYan
447 5
RossyYan
|
存储 算法 安全
【C语言程序设计——选择结构程序设计】按从小到大排序三个数（头歌实践教学平台习题）【合集】
本任务要求从键盘输入三个数，并按从小到大的顺序排序后输出。主要内容包括： - **任务描述**：实现三个数的排序并输出。 - **编程要求**：根据提示在编辑器中补充代码。 - **相关知识**： - 选择结构（if、if-else、switch） - 主要语句类型（条件语句） - 比较操作与交换操作 - **测试说明**：提供两组测试数据及预期输出。 - **通关代码**：完整代码示例。 - **测试结果**：展示测试通过的结果。 通过本任务，你将掌握基本的选择结构和排序算法的应用。祝你成功！
RossyYan
405 4
ephemerals__
|
搜索推荐 算法 C语言
【排序算法】八大排序（下）（c语言实现）（附源码）
本文继续学习并实现了八大排序算法中的后四种：堆排序、快速排序、归并排序和计数排序。详细介绍了每种排序算法的原理、步骤和代码实现，并通过测试数据展示了它们的性能表现。堆排序利用堆的特性进行排序，快速排序通过递归和多种划分方法实现高效排序，归并排序通过分治法将问题分解后再合并，计数排序则通过统计每个元素的出现次数实现非比较排序。最后，文章还对比了这些排序算法在处理一百万个整形数据时的运行时间，帮助读者了解不同算法的优劣。
ephemerals__
738 7
疯狂的猿
|
C语言 Windows
C语言课设项目之2048游戏源码
C语言课设项目之2048游戏源码，可作为课程设计项目参考，代码有详细的注释，另外编译可运行文件也已经打包，windows电脑双击即可运行效果
疯狂的猿
298 1
RossyYan
|
存储 算法 安全
【C语言程序设计——选择结构程序设计】求阶跃函数的值（头歌实践教学平台习题）【合集】
本任务要求输入x的值，计算并输出特定阶跃函数的结果。主要内容包括： 1. **选择结构基本概念**：介绍if、if-else、switch语句。 2. **主要语句类型**：详细解释if、if-else、switch语句的使用方法。 3. **跃迁函数中变量的取值范围**：说明如何根据条件判断变量范围。 4. **计算阶跃函数的值**：通过示例展示如何根据给定条件计算函数值。 编程要求：在右侧编辑器Begin-End之间补充代码，实现阶跃函数的计算和输出。测试说明提供了多个输入及其预期输出，确保代码正确性。最后提供通关代码和测试结果，帮助理解整个过程。
RossyYan
416 0
RossyYan
|
存储 算法 安全
【C语言程序设计——选择结构程序设计】判断一个数是不是5和7的倍数（头歌实践教学平台习题）【合集】
本任务要求输入一个正整数，判断其是否同时是5和7的倍数，若是输出&quot;Yes&quot;，否则输出&quot;No&quot;。内容涵盖选择结构的基本概念、主要语句类型（if、if-else、switch）及条件判断逻辑，帮助理解编程中的分支执行与条件表达式。测试用例包括正数、负数及非倍数情况，确保代码逻辑严谨。通关代码示例如下： ```cpp #include &quot;stdio.h&quot; int main(){ int a; scanf(&quot;%d&quot;, &a); if (a &lt;= 0){ printf(&quo
RossyYan
800 0
RossyYan
|
编译器 C语言 C++
【C语言程序设计——选择结构程序设计】求输入的日期是该年的第几天（头歌实践教学平台习题）【合集】
本任务要求编写程序，根据用户输入的年月日（以空格或回车分隔），计算并输出该天是该年的第几天，需注意判断闰年。主要内容包括： 1. **任务描述**：实现从键盘输入年月日，计算该天是当年的第几天。 2. **相关知识**： - `switch` 结构的基本语法及使用注意事项。 - 判断闰年的条件：能被4整除但不能被100整除，或能被400整除的年份为闰年。 3. **编程要求**：根据提示补充代码，确保程序正确处理输入并输出结果。 4. **测试说 示例代码展示了如何使用 `switch` 语句和闰年判断逻辑来完成任务。通过此练习，掌握 `switch` 语句的应用及闰年判断方法。
RossyYan
736 0

热门文章

最新文章

  • 1
    C语言算法--桶排序
  • 2
    【C语言】符号优先级详解 -《谁与争锋 ! 》
  • 3
    C语言位运算符详解
  • 4
    C语言入门——常用转义字符
  • 5
    【C语言基础考研向】05 scanf读取标准输入超详解
  • 6
    C语言与硬件交互：通过I/O端口控制硬件。
  • 7
    C语言的一个关键字——static
  • 8
    C语言---试计算在区间1 到n 的所有整数中，数字x（0 ≤ x ≤ 9）共出现了多少次？
  • 9
    【C 语言】指针间接赋值 ( 直接修改 和 间接修改 指针变量 的值 | 在函数中 间接修改 指针变量 的值 | 在函数中 间接修改 外部变量 的原理 )
  • 10
    KMP算法C语言实现。弄了好久才搞好。。。
  • 1
    c语言文件操作
    400
  • 2
    `scanf`是C语言中用于按格式读取标准输入的函数
    1616
  • 3
    基于标准C语言实现的跨平台Modbus协议库
    705
  • 4
    C语言常见概念
    779
  • 5
    C语言中的字符、字符串及内存操作函数详细讲解
    574
  • 6
    比较C++的内存分配与管理方式new/delete与C语言中的malloc/realloc/calloc/free。
    461
  • 7
    c语言的文件操作与文件缓冲区
    666
  • 8
    c语言——二叉树
    370
  • 9
    C语言分支和循环语句
    329
  • 10
    C语言与操作系统交互探秘
    593

    • 相关课程

    更多
  • 你的第一门C语言课
  • C语言学习教程

    • 相关电子书

    更多
  • 低代码开发师（初级）实战教程
  • 冬季实战营第三期：MySQL数据库进阶实战
  • 阿里巴巴DevOps 最佳实践手册
    • 下一篇
    一条命令迁移，帮你实现 OpenClaw 与 Hermes Agent 记忆互通！