[数据结构 -- C语言] 堆(Heap),你小子就是堆,看我如何透彻的将你拿捏

简介: [数据结构 -- C语言] 堆(Heap),你小子就是堆,看我如何透彻的将你拿捏

1、堆的概念及结构

1.1 概念(概念总是重要的)


上面这一段是堆的概念,但是这也太没劲了吧,我们来通俗的讲一下,敲黑板了嗷:


堆的本质是一个完全二叉树。


大堆(也叫大根堆):父节点大于/等于子节点。


小对(也叫小根堆):父节点小于/等于子节点。


如果不满足上面的条件,那么就不是堆。


堆的性质:


1、堆中某个节点的值总是不大于或不小于其父节点的值;

2、堆总是一棵完全二叉树。

1.2 结构,分为两种

1.2.1 小堆/小根堆示例



1.2.2 大堆/大根堆示例


我们来看一个题目:


下列关键字序列为堆的是:(A)


A 100,60,70,50,32,65


B 60,70,65,50,32,100


C 65,100,70,32,50,60


D 70,65,100,32,50,60


E 32,50,100,70,65,60


F 50,100,70,65,60,32


分析:我们画图来分析



2、堆的接口

本篇文章是以小堆为例来实现的。堆的数据存储是用数组存的,数据的内存中的存储结构是顺序存储的,我们为了好理解,以逻辑结构理解的。

堆的接口有:初始化、销毁、插入、删除、取堆顶、堆的数据个数、判空。

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
typedef int HPDataType;
typedef struct Heap
{
  HPDataType* a;
  int size;
  int capacity;
}Heap;
// 堆的初始化
void HeapInit(Heap* hp);
// 堆的销毁
void HeapDestory(Heap* hp);
//交换
void Swap(HPDataType* p1, HPDataType* p2);
//向上调整
void AdjustUp(HPDataType* a, int child);
//向下调整
void AdjustDown(HPDataType* a, int size, int parent);
// 堆的插入
void HeapPush(Heap* hp, HPDataType x);
// 堆的删除
void HeapPop(Heap* hp);
// 取堆顶的数据
HPDataType HeapTop(Heap* hp);
// 堆的数据个数
int HeapSize(Heap* hp);
// 堆的判空
bool HeapEmpty(Heap* hp);

3、接口实现

我们这些接口好多都是与之前的数据结构文章是类似的,前面已经多次讲解,这里就不再讲解了,要是有看不懂的地方可以参考之前的数据结构文章。

3.1 堆的初始化

void HeapInit(Heap* hp)
{
  assert(hp);
  hp->a = NULL;
  hp->size = 0;
  hp->capacity = 0;
}

3.2 堆的销毁

void HeapDestory(Heap* hp)
{
  assert(hp);
  free(hp->a);
  hp->a = NULL;
  hp->size = hp->capacity = 0;
}

3.3 堆的插入

堆的插入是比较复杂的,也是一个难点,我们先来分析,再去实现功能。

功能分析:

1、插入的时候我们先要看数组是否需要扩容,先判满,如果空间满了就先扩容,然后将新元素插入到数组的尾部;
2、我们新插入一个元素,就需要去分析一下此堆是否满足小堆的结构,如果不满足我们就需要将新元素向上调整。

3、向上调整过程分析:

我们来举例分析一下:如果给一个小堆插入一个元素后,堆的结构被破坏,如何调整才能恢复小堆的结构。



a、当我们发现给小堆插入一个 10 后,10 比父节点 28 小,破坏了小堆的结构,我们需要对堆进行调整;


b、堆的物理结构是数组,所以我们可以通过下标来找到父节点,这里找父节点的公式:parent = (child-1)/2。当我们找到父节点后,让子节点与父节点去比较,如果小于父节点我们就让两个节点的元素交换,交换后的父节点与它的父节点可能也不满足小堆,因此需要不断的向上调整;


c、循环去比较调整,当child = 0 时,我们的调整就结束了,因此我们的循环判断条件为 child > 0。


注意:当有一次调整完后,我们的堆已经成为了小堆,就跳出循环。


我们根据上面的思路来画图走一遍:




我们对功能的分析就结束了,开始实现功能。

功能实现:

void Swap(HPDataType* p1, HPDataType* p2)
{
  HPDataType tmp = *p1;
  *p1 = *p2;
  *p2 = tmp;
}
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;
    }
  }
}
//log N 
void HeapPush(Heap* hp, HPDataType x)
{
  assert(hp);
  if (hp->size == hp->capacity)
  {
    int newcapacity = hp->capacity == 0 ? 4 : 2 * hp->capacity;
    HPDataType* tmp = (HPDataType*)realloc(hp->a, sizeof(HPDataType) * newcapacity);
    if (NULL == tmp)
    {
      perror("realloc fail:");
    }
    hp->a = tmp;
    hp->capacity = newcapacity;
  }
  hp->a[hp->size] = x;
  hp->size++;
  AdjustUp(hp->a, hp->size - 1);
}

交换与向上调整后面我们会复用的,因此我们将其两个功能封装成函数。

3.4 堆的删除

堆的删除是删堆顶的元素。

思路:堆顶数据与最后一个数据交换,删掉最后一个数据,再从堆顶向下调整。

功能分析:

我们这里删除堆顶数据的时候不能直接删,直接删除堆顶数据就会破坏堆结构,再去建堆时间复杂度太高,不推荐,这里我们介绍一种方法,复杂度较低:
1、我们将堆顶数据与最后一个数据先交换,再删除最后一个数据,最后从堆顶向下调整;


2、向下调整比较复杂,我们下面进行分析并画图来讲解:


a、此时我们的 parent节点 是堆顶节点,接下来我们需要找到 2 个子节点中小的哪个作为孩子节点,这里的找子节点公式:child = parent*2 + 1;


b、如果孩子小于父亲,就交换,并且继续往下调整,让parent 走到 child 位置,再去算 child 位置;


c、当孩子下标大于数组的大小时,循环就结束,整个调整就完成了。


注意:当有一次调整完后,我们的堆已经成为了小堆,就跳出循环。

功能实现:

void AdjustDown(HPDataType* a, int size, int parent)
{
  int child = parent * 2 + 1;
  while (child < size)//当child大于了数组大小就跳出循环
  {
    //找出左右孩子中小/大的那个(假设法)
    if (child + 1 < size && a[child + 1] < a[child])
    {
      child++;
    }
    if (a[child] < a[parent])
    {
      Swap(&a[parent], &a[child]);
      parent = child;
      child = parent * 2 + 1;
    }
    else
    {
      break;
    }
  }
}
//log N
void HeapPop(Heap* hp)
{
  assert(hp);
  assert(!HeapEmpty(hp));
  Swap(&hp->a[0], &hp->a[hp->size - 1]);
  hp->size--;
  AdjustDown(hp->a, hp->size, 0);
}

3.5 取堆顶的数据

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

3.6 堆的数据个数

int HeapSize(Heap* hp)
{
  assert(hp);
  assert(!HeapEmpty(hp));
  return hp->size;
}

3.7 堆的判空

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

4、完整代码

完整代码在代码仓库:Heap · 小白在努力jy/DataStructure - 码云 - 开源中国 (gitee.com)

相关文章
|
22天前
|
算法 数据处理 C语言
C语言中的位运算技巧,涵盖基本概念、应用场景、实用技巧及示例代码,并讨论了位运算的性能优势及其与其他数据结构和算法的结合
本文深入解析了C语言中的位运算技巧,涵盖基本概念、应用场景、实用技巧及示例代码,并讨论了位运算的性能优势及其与其他数据结构和算法的结合,旨在帮助读者掌握这一高效的数据处理方法。
34 1
|
1月前
|
存储 算法 搜索推荐
【趣学C语言和数据结构100例】91-95
本文涵盖多个经典算法问题的C语言实现,包括堆排序、归并排序、从长整型变量中提取偶数位数、工人信息排序及无向图是否为树的判断。通过这些问题,读者可以深入了解排序算法、数据处理方法和图论基础知识,提升编程能力和算法理解。
45 4
|
1月前
|
存储 机器学习/深度学习 搜索推荐
【趣学C语言和数据结构100例】86-90
本文介绍并用C语言实现了五种经典排序算法:直接插入排序、折半插入排序、冒泡排序、快速排序和简单选择排序。每种算法都有其特点和适用场景,如直接插入排序适合小规模或基本有序的数据,快速排序则适用于大规模数据集,具有较高的效率。通过学习这些算法,读者可以加深对数据结构和算法设计的理解,提升解决实际问题的能力。
43 4
|
1月前
|
存储 算法 数据处理
【趣学C语言和数据结构100例】81-85
本文介绍了五个经典算法问题及其C语言实现,涵盖图论与树结构的基础知识。包括使用BFS求解单源最短路径、统计有向图中入度或出度为0的点数、统计无向无权图各顶点的度、折半查找及二叉排序树的查找。这些算法不仅理论意义重大,且在实际应用中极为广泛,有助于提升编程能力和数据结构理解。
38 4
|
1月前
|
算法 数据可视化 数据建模
【趣学C语言和数据结构100例】76-80
本文介绍了五种图论算法的C语言实现,涵盖二叉树的层次遍历及广度优先搜索(BFS)和深度优先搜索(DFS)的邻接表与邻接矩阵实现。层次遍历使用队列按层访问二叉树节点;BFS利用队列从源节点逐层遍历图节点,适用于最短路径等问题;DFS通过递归或栈深入图的分支,适合拓扑排序等场景。这些算法是数据结构和算法学习的基础,对提升编程能力和解决实际问题至关重要。
48 4
|
1月前
|
存储 算法 vr&ar
【趣学C语言和数据结构100例】71-75
本文介绍了五个C语言数据结构问题及其实现,涵盖链表与二叉树操作,包括按奇偶分解链表、交换二叉树左右子树、查找节点的双亲节点、计算二叉树深度及求最大关键值。通过递归和遍历等方法,解决了理论与实际应用中的常见问题,有助于提升编程能力和数据结构理解。
37 4
|
1月前
|
存储 算法 C语言
【趣学C语言和数据结构100例】66-70
本书《趣学C语言和数据结构100例》精选了5个典型的数据结构问题及C语言实现,涵盖链表与数组操作,如有序集合的集合运算、有序序列表的合并、数组中两顺序表位置互换、三递增序列公共元素查找及奇偶数重排。通过详细解析与代码示例,帮助读者深入理解数据结构与算法设计的核心思想,提升编程技能。
33 4
|
23天前
|
存储 缓存 算法
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式,强调了合理选择数据结构的重要性,并通过案例分析展示了其在实际项目中的应用,旨在帮助读者提升编程能力。
44 5
|
22天前
|
并行计算 算法 测试技术
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略,涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略,涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面,旨在通过综合策略提升程序性能,满足实际需求。
52 1
|
1月前
|
存储 机器学习/深度学习 算法
【趣学C语言和数据结构100例】61-65
本文介绍了五个关于C语言和数据结构的经典问题及其实现方法,涵盖查找链表共同后缀、删除重复节点、重新排列链表元素、合并有序链表以及特定条件下的链表排序。每个问题通过具体的算法设计,不仅展示了链表操作的灵活性,还强调了效率优化的重要性。通过这些问题的探讨,读者可以深入理解链表的基本操作和高级应用,提升解决实际问题的能力。
46 4