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

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

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


文章标签：
算法
存储
关键词：
C语言二叉树
C语言概念
C语言源码
C语言顺序结构
二叉树C语言
花想云
目录
相关文章
c的前世今生
|
12天前
|
存储 编译器 程序员
C语言程序的基本结构
C语言程序的基本结构包括：1）预处理指令，如 `#include` 和 `#define`；2）主函数 `main()`，程序从这里开始执行；3）函数声明与定义，执行特定任务的代码块；4）变量声明与初始化，用于存储数据；5）语句和表达式，构成程序基本执行单位；6）注释，解释代码功能。示例代码展示了这些组成部分的应用。
c的前世今生
27 10
小徐在进步
|
11天前
|
C语言
C语言程序设计核心详解 第四章&&第五章 选择结构程序设计&&循环结构程序设计
本章节介绍了C语言中的选择结构，包括关系表达式、逻辑表达式及其运算符的优先级，并通过示例详细解释了 `if` 语句的不同形式和 `switch` 语句的使用方法。此外，还概述了循环结构，包括 `while`、`do-while` 和 `for` 循环，并解释了 `break` 和 `continue` 控制语句的功能。最后，提供了两道例题以加深理解。
小徐在进步
44 7
小徐在进步
|
11天前
|
存储 算法 C语言
数据结构基础详解(C语言): 二叉树的遍历_线索二叉树_树的存储结构_树与森林详解
本文从二叉树遍历入手，详细介绍了先序、中序和后序遍历方法，并探讨了如何构建二叉树及线索二叉树的概念。接着，文章讲解了树和森林的存储结构，特别是如何将树与森林转换为二叉树形式，以便利用二叉树的遍历方法。最后，讨论了树和森林的遍历算法，包括先根、后根和层次遍历。通过这些内容，读者可以全面了解二叉树及其相关概念。
小徐在进步
25 6
小徐在进步
|
11天前
|
C语言
C语言程序设计核心详解 第三章:顺序结构，printf(),scanf()详解
本章介绍顺序结构的基本框架及C语言的标准输入输出。程序从`main()`开始依次执行，框架包括输入、计算和输出三部分。重点讲解了`printf()`与`scanf()`函数：`printf()`用于格式化输出，支持多种占位符；`scanf()`用于格式化输入，需注意普通字符与占位符的区别。此外还介绍了`putchar()`和`getchar()`函数，分别用于输出和接收单个字符。
小徐在进步
21 5
小徐在进步
|
11天前
|
存储 机器学习/深度学习 C语言
数据结构基础详解(C语言): 树与二叉树的基本类型与存储结构详解
本文介绍了树和二叉树的基本概念及性质。树是由节点组成的层次结构，其中节点的度为其分支数量，树的度为树中最大节点度数。二叉树是一种特殊的树，其节点最多有两个子节点，具有多种性质，如叶子节点数与度为2的节点数之间的关系。此外，还介绍了二叉树的不同形态，包括满二叉树、完全二叉树、二叉排序树和平衡二叉树，并探讨了二叉树的顺序存储和链式存储结构。
小徐在进步
14 3
小徐在进步
|
10天前
|
存储 算法 C语言
C语言手撕实战代码_二叉树_构造二叉树_层序遍历二叉树_二叉树深度的超详细代码实现
这段代码和文本介绍了一系列二叉树相关的问题及其解决方案。其中包括根据前序和中序序列构建二叉树、通过层次遍历序列和中序序列创建二叉树、计算二叉树节点数量、叶子节点数量、度为1的节点数量、二叉树高度、特定节点子树深度、判断两棵树是否相似、将叶子节点链接成双向链表、计算算术表达式的值、判断是否为完全二叉树以及求二叉树的最大宽度等。每道题目均提供了详细的算法思路及相应的C/C++代码实现，帮助读者理解和掌握二叉树的基本操作与应用。
小徐在进步
12 2
小徐在进步
|
11天前
|
存储 C语言
数据结构基础详解(C语言): 树与二叉树的应用_哈夫曼树与哈夫曼曼编码_并查集_二叉排序树_平衡二叉树
本文详细介绍了树与二叉树的应用，涵盖哈夫曼树与哈夫曼编码、并查集以及二叉排序树等内容。首先讲解了哈夫曼树的构造方法及其在数据压缩中的应用；接着介绍了并查集的基本概念、存储结构及优化方法；随后探讨了二叉排序树的定义、查找、插入和删除操作；最后阐述了平衡二叉树的概念及其在保证树平衡状态下的插入和删除操作。通过本文，读者可以全面了解树与二叉树在实际问题中的应用技巧和优化策略。
小徐在进步
17 2
aliyun6365824167
|
1月前
|
算法 编译器 C语言
【C语言篇】猜数字游戏（赋源码）
rand函数会返回⼀个伪随机数，这个随机数的范围是在0~RAND_MAX之间，这个RAND_MAX的⼤⼩是依赖编译器上实现的，但是⼤部分编译器上是32767。
aliyun6365824167
49 1
aliyun6365824167
|
1月前
|
机器学习/深度学习 C语言
【C语言篇】递归详细介绍（基础概念习题及汉诺塔等进阶问题）
要保持最小的步数，每一次汉诺塔问题（无论是最初还是递归过程中的），如果此时初始柱盘子数为偶数，我们第一步是把最上面的盘子移动到中转柱，如果为奇数，我们第一步则是将其移动到目标柱。
aliyun6365824167
35 0
【C语言篇】递归详细介绍（基础概念习题及汉诺塔等进阶问题）
芯动大师
|
23天前
|
机器学习/深度学习 存储 C语言
C语言的二叉树
1.树概念及结构 1.1树的概念 树是一种非线性的数据结构，它是由n（n>=0）个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。 补充定义: 有一个特殊的结点，称为根结点，根节点没有前驱结点。除根节点外，其余结点被分成M(M>0)个互不相交的集合T1、T2、……、Tm，其中每一个集合Ti(1<= i <= m)又是一棵结构与树类似的子树。每棵子树的根结点有且只有一个前驱，可以有0个或多个后继。因此，树是递归定义的。 1.2 树的相关概念 节点的度：一个节点含有的子树的个数称为该节点的度； 如上图：A的为6 叶节点或终端
芯动大师
11 0