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

＜堆及堆排序＞《数据结构(C语言版)》

2022-11-27 174
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： ＜堆及堆排序＞《数据结构(C语言版)》

目录

《数据结构(C语言版)》实战项目之堆及堆排序的功能实现                                                                                   ——By 作者：新晓·故知

一、完整源码：

完整源码如下，欢迎复制测试指正！

堆及堆排序的功能实现测试示例：

完整源码：

二、堆及堆排序实现分析：

1.堆的概念及结构

2.堆的实现

2.1 堆向下调整算法

2.2堆的创建

2.3 建堆时间复杂度

2.4 堆的插入

2.5 堆的删除

2.6 堆的代码实现

（1）堆的初始化

（2）堆的打印

（3）堆的销毁

（4）堆的交换

（5）堆的向上调整

（6）堆的向下调整

（7）堆的插入

（8）堆的删除（堆顶元素）

（9）判断堆是否为空

（10）求堆的大小

（11）取堆顶元素

3. 堆的应用

3.1 堆排序

后记：●由于作者水平有限，文章难免存在谬误之处，敬请读者斧正，俚语成篇，恳望指教！

                                                                          ——By 作者：新晓·故知

《数据结构(C语言版)》实战项目之堆及堆排序的功能实现

                                                                            ——By 作者：新晓·故知

一、完整源码：

完整源码如下，欢迎复制测试指正！

堆及堆排序的功能实现测试示例： image.gif编辑

image.gif编辑image.gif编辑

image.gif编辑 调试测试：

image.gif编辑image.gif编辑

完整源码：

Test.c:

#include"Heap.h"
//堆的实现
//这里采用小堆法
//堆的插入测试
void TestHeap1()
{
  HP hp;
  HeapInit(&hp);
  //1.一个一个创建数据(可随机，可乱序）
  HeapPush(&hp, 7);
  HeapPush(&hp, 1);
  HeapPush(&hp, 5);
  HeapPush(&hp, 6);
  HeapPush(&hp, 4);
  HeapPush(&hp, 9);
  HeapPrint(&hp);
  ////2.使用循环创建数据（只能有序创建）
  //for (int i = 0; i < 5; i++)
  //{
  //  HeapPush(&hp, i);
  //}
  //HeapPrint(&hp);
  HeapDestroy(&hp);
}
//堆顶删除元素测试
void TestHeap2()
{
  HP hp;
  HeapInit(&hp);
  //1.一个一个创建数据(可随机，可乱序）
  HeapPush(&hp, 7);
  HeapPush(&hp, 1);
  HeapPush(&hp, 5);
  HeapPush(&hp, 6);
  HeapPush(&hp, 4);
  HeapPush(&hp, 9);
  HeapPrint(&hp);
  //删除堆顶元素
  HeapPop(&hp);
  HeapPrint(&hp);
}
//求堆大小测试
void TestHeap3()
{
  HP hp;
  HeapInit(&hp);
  //1.一个一个创建数据(可随机，可乱序）
  HeapPush(&hp, 7);
  HeapPush(&hp, 1);
  HeapPush(&hp, 5);
  HeapPush(&hp, 6);
  HeapPush(&hp, 4);
  HeapPush(&hp, 9);
  HeapPrint(&hp);
  int i=HeapSize(&hp);
  printf("%d ", i);
}
//取堆顶元素测试
void TestHeap4()
{
  HP hp;
  HeapInit(&hp);
  //1.一个一个创建数据(可随机，可乱序）
  HeapPush(&hp, 7);
  HeapPush(&hp, 1);
  HeapPush(&hp, 5);
  HeapPush(&hp, 6);
  HeapPush(&hp, 4);
  HeapPush(&hp, 9);
  HeapPrint(&hp);
  int i=HeapTop(&hp);
  printf("%d ", i);
}
//堆排序测试—（升序）
//如果（降序），只需更改Heap.c中的注释判断部分
//1.交换-删除-调整法:
//时间复杂度: O（N* logN)
//空间复杂度: O(N)
//优化：建堆    空间：O（1）
//2.覆盖法：
//时间复杂度： O（N^2)
////堆排序-1
//时间复杂度: O（N* logN)
//空间复杂度: O(N)
//void HeapSort(int* a, int size)
//{
//  HP hp;
//  HeapInit(&hp);
//  //O（N* logN)
//  for (int i = 0; i < size; ++i)
//  {
//    HeapPush(&hp, a[i]);
//  }
//  //O（N* logN)
//  size_t j = 0;
//  while (!HeapEmpty(&hp))
//  {
//    a[j] = HeapTop(&hp);
//    j++;
//    HeapPop(&hp);
//  }
//
//  HeapDestroy(&hp);
//
//}
//建堆算法
//堆排序-1++  优化：建堆
//时间复杂度:O（N* logN)、
//空间复杂度:O（1）
//直接在原数组建堆
void HeapSort(int* a, int n)
{
  ////建堆1.——向上调整   时间复杂度:O（N* logN)
  //for (int i = 1; i < n;++i)
  //{
  //  AdjustUp(a, i);
  //}
  //建堆2.——向下调整     时间复杂度:O（N)
  //不能直接建堆，因为向下调整函数功能有要求
  //从倒数第一个非叶子结点（最后一个叶子结点的父亲）开始
  for (int i = (n - 1 - 1) / 2;i >= 0; --i)
  {
    AdjustDown(a, n, i);
  }
  //交换调整
  size_t end = n - 1;
  while (end>0)
  {
    Swap(&a[0], &a[end]);
    AdjustDown(a, end, 0);
    --end;
  }
}
int main()
{
  //TestHeap1();
  //TestHeap2();
  //TestHeap3();
  //TestHeap4();
  int a[] = { 4,2,7,8,5,1,0,6 };
  HeapSort(a, sizeof(a) / sizeof(int));
  for (int i = 0; i < sizeof(a) / sizeof(int); ++i)
  {
    printf("%d ", a[i]);
  }
  printf("\n");
  return 0;
}
image.gif

Heap.c:

#include"Heap.h"
//堆的实现
//这里采用小堆法
//堆的实现操纵的是数组，想象的是二叉树结构！！！
//堆的功能函数
//堆的初始化
void HeapInit(HP* php)
{
  assert(php);
  php->a = NULL;
  php->size = php->capacity = 0;
}
//堆的打印
void HeapPrint(HP* php)
{
  assert(php);
  for (size_t i = 0; i < php->size; i++)
  {
    printf("%d ", php->a[i]);
  }
  printf("\n");
}
//堆的销毁
void HeapDestroy(HP* php)
{
  assert(php);
  free(php->a);
  php->a = NULL;
  php->size = php->capacity = 0;
}
//堆的交换
void Swap(HPDataType* pa, HPDataType* pb)
{
  HPDataType tmp = *pa;
  *pa = *pb;
  *pb = tmp;
}
//堆的向上调整
void AdjustUp(HPDataType* a, size_t child)
{
  size_t parent = (child - 1) / 2;
  while (child > 0)
  {
    //小堆-升序
    //if (a[child] < a[parent]) 
    ////大堆-降序
    //if (a[child] > a[parent])
    //升序要建大堆（根据建堆分析）
    if (a[child] > a[parent])
    {
      Swap(&a[child], &a[parent]);
      child = parent;
      parent = (child - 1) / 2;
    }
    else
    {
      break;
    }
  }
}
//堆的插入（插入x以后，保持其依旧是小堆/大堆）
void HeapPush(HP* php, HPDataType x)
{
  assert(php);
  if (php->size == php->capacity)
  {
    size_t newCapacity = php->capacity == 0 ? 4 : php->capacity * 2;
    HPDataType* tmp = realloc(php->a, sizeof(HPDataType) * newCapacity);
    //HPDataType* tmp 这样做，如果relloc失败，不会将原来的空间覆盖为0
    //如果php->a最初为0，则相当于malloc
    //在栈的实现中没有这样做，栈的实现有缺陷，要注意！
    if (tmp == NULL)
    {
      printf("relloc falied\n");
      exit(-1);
    }
    php->a = tmp;
    php->capacity = newCapacity;
  }
  php->a[php->size] = x;
  ++php->size;
  //向上调整，控制保持是一个小堆
  AdjustUp(php->a, php->size - 1);
}
//向下调整
void AdjustDown(HPDataType* a, size_t size, size_t root)
{
  size_t parent = root;
  size_t child = parent * 2 + 1;
  while (child < size)
  {
    //1.选出左右孩子中小的那个
    //小堆-升序
    //if (child + 1 < size && a[child +1] < a[child])
    //大堆-降序
    //if (child + 1 < size && a[child + 1] >a[child])
    //升序要建大堆（根据建堆分析）
    if (child + 1 < size && a[child + 1] >a[child])
    {
      ++child;
      }
    //2.如果孩子小于父亲，则交换，并继续向下调整
    //if (a[child] < a[parent])  //小堆-升序
    //if (a[child] > a[parent])  //大堆-降序
    //升序要建大堆（根据建堆分析）
    if (a[child] >a[parent])
    {
      Swap(&a[child], &a[parent]);
      parent = child;
      child = parent * 2 + 1;
    }
    else
    {
      break;
    }
  }
}
//堆的删除（删除堆顶的数据，该数据是最小/最大）
void HeapPop(HP* php)
{
  assert(php);
  Swap(&php->a[0], &php->a[php->size - 1]);
  --php->size;
  //向下调整
  AdjustDown(php->a, php->size, 0);
}
//判断堆是否为空
bool HeapEmpty(HP* php)
{
  assert(php);
  return php->size == 0;
}
//求堆的大小
size_t HeapSize(HP* php)
{
  assert(php);
  return php->size;
}
//取堆顶
HPDataType HeapTop(HP* php)
{
  assert(php);
  assert(php->size > 0);
  return php->a[0];
}
image.gif

Heap.h:

#pragma once
//堆的实现
//这里采用小堆法
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>
//堆的底层物理结构上是一个数组（动态增长），逻辑上是一个完全二叉树
//动态结构——方便（也可使用静态结构）
typedef int HPDataType;
typedef struct Heap
{
  HPDataType* a;
  size_t size;
  size_t capacity;
}HP;
//堆的初始化
void HeapInit(HP* php);
//这个是将数组拷贝，使用建堆算法
//void HeapInitArray(HP* php, HPDataType*a,size_t n);
//堆的销毁
void HeapDestroy(HP* php);
//堆的插入（插入x以后，保持其依旧是小堆/大堆）
void HeapPush(HP* php, HPDataType x);
//堆的删除（删除堆顶的数据，该数据是最小/最大）
void HeapPop(HP* php);
//堆的交换
void Swap(HPDataType* pa, HPDataType* pb);
//堆的打印
void HeapPrint(HP* php);
//判断堆是否为空
bool HeapEmpty(HP* php);
//求堆的大小
size_t HeapSize(HP* php);
//取堆顶
HPDataType HeapTop(HP* php);
//向上调整
void AdjustUp(HPDataType* a, size_t child);
//向下调整
void AdjustDown(HPDataType* a, size_t size, size_t root);
image.gif

二、堆及堆排序实现分析：

1.堆的概念及结构

image.gif编辑

堆的性质：

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

堆总是一棵完全二叉树。

image.gif编辑

2.堆的实现

2.1 堆向下调整算法

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

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

 image.gif编辑

2.2堆的创建

下面我们给出一个数组，这个数组逻辑上可以看做一颗完全二叉树，但是还不是一个堆，现在我们通过算法，把它构建成一个堆。根节点左右子树不是堆，我们怎么调整呢？这里我们从倒数的第一个非叶子节点的子树开始调整，一直调整到根节点的树，就可以调整成堆。

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

image.gif编辑

2.3 建堆时间复杂度

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

 

image.gif编辑

因此：建堆的时间复杂度为O(N)。

2.4 堆的插入

先插入一个10到数组的尾上，再进行向上调整算法，直到满足堆。

image.gif编辑

2.5 堆的删除

删除堆是删除堆顶的数据，将堆顶的数据根最后一个数据一换，然后删除数组最后一个数据，再进行向下调整算法。

image.gif编辑

2.6 堆的代码实现

（1）堆的初始化

//堆的初始化
void HeapInit(HP* php)
{
  assert(php);
  php->a = NULL;
  php->size = php->capacity = 0;
}
image.gif

（2）堆的打印

//堆的打印
void HeapPrint(HP* php)
{
  assert(php);
  for (size_t i = 0; i < php->size; i++)
  {
    printf("%d ", php->a[i]);
  }
  printf("\n");
}
image.gif

（3）堆的销毁

//堆的销毁
void HeapDestroy(HP* php)
{
  assert(php);
  free(php->a);
  php->a = NULL;
  php->size = php->capacity = 0;
}
image.gif

（4）堆的交换

//堆的交换
void Swap(HPDataType* pa, HPDataType* pb)
{
  HPDataType tmp = *pa;
  *pa = *pb;
  *pb = tmp;
}
image.gif

（5）堆的向上调整

//堆的向上调整
void AdjustUp(HPDataType* a, size_t child)
{
  size_t parent = (child - 1) / 2;
  while (child > 0)
  {
    //小堆-升序
    //if (a[child] < a[parent]) 
    ////大堆-降序
    //if (a[child] > a[parent])
    //升序要建大堆（根据建堆分析）
    if (a[child] > a[parent])
    {
      Swap(&a[child], &a[parent]);
      child = parent;
      parent = (child - 1) / 2;
    }
    else
    {
      break;
    }
  }
}
image.gif

（6）堆的向下调整

//向下调整
void AdjustDown(HPDataType* a, size_t size, size_t root)
{
  size_t parent = root;
  size_t child = parent * 2 + 1;
  while (child < size)
  {
    //1.选出左右孩子中小的那个
    //小堆-升序
    //if (child + 1 < size && a[child +1] < a[child])
    //大堆-降序
    //if (child + 1 < size && a[child + 1] >a[child])
    //升序要建大堆（根据建堆分析）
    if (child + 1 < size && a[child + 1] >a[child])
    {
      ++child;
      }
    //2.如果孩子小于父亲，则交换，并继续向下调整
    //if (a[child] < a[parent])  //小堆-升序
    //if (a[child] > a[parent])  //大堆-降序
    //升序要建大堆（根据建堆分析）
    if (a[child] >a[parent])
    {
      Swap(&a[child], &a[parent]);
      parent = child;
      child = parent * 2 + 1;
    }
    else
    {
      break;
    }
  }
}
image.gif

（7）堆的插入

//堆的插入（插入x以后，保持其依旧是小堆/大堆）
void HeapPush(HP* php, HPDataType x)
{
  assert(php);
  if (php->size == php->capacity)
  {
    size_t newCapacity = php->capacity == 0 ? 4 : php->capacity * 2;
    HPDataType* tmp = realloc(php->a, sizeof(HPDataType) * newCapacity);
    //HPDataType* tmp 这样做，如果relloc失败，不会将原来的空间覆盖为0
    //如果php->a最初为0，则相当于malloc
    //在栈的实现中没有这样做，栈的实现有缺陷，要注意！
    if (tmp == NULL)
    {
      printf("relloc falied\n");
      exit(-1);
    }
    php->a = tmp;
    php->capacity = newCapacity;
  }
  php->a[php->size] = x;
  ++php->size;
  //向上调整，控制保持是一个小堆
  AdjustUp(php->a, php->size - 1);
}
image.gif

（8）堆的删除（堆顶元素）

//堆的删除（删除堆顶的数据，该数据是最小/最大）
void HeapPop(HP* php)
{
  assert(php);
  Swap(&php->a[0], &php->a[php->size - 1]);
  --php->size;
  //向下调整
  AdjustDown(php->a, php->size, 0);
}
image.gif

（9）判断堆是否为空

//判断堆是否为空
bool HeapEmpty(HP* php)
{
  assert(php);
  return php->size == 0;
}
image.gif

（10）求堆的大小

//求堆的大小
size_t HeapSize(HP* php)
{
  assert(php);
  return php->size;
}
image.gif

（11）取堆顶元素

//取堆顶
HPDataType HeapTop(HP* php)
{
  assert(php);
  assert(php->size > 0);
  return php->a[0];
}
image.gif

3. 堆的应用

3.1 堆排序

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

1. 建堆

      ★升序：建大堆

      ★降序：建小堆

2. 利用堆删除思想来进行排序

建堆和堆删除中都用到了向下调整，因此掌握了向下调整，就可以完成堆排序。

image.gif编辑

image.gif编辑

后记：

●由于作者水平有限，文章难免存在谬误之处，敬请读者斧正，俚语成篇，恳望指教！

                                                                          ——By 作者：新晓·故知

文章标签：
算法
关键词：
数据结构c语言
C语言数据结构
堆数据结构
数据结构堆排序
堆排序数据结构
新晓故知
目录
相关文章
ephemerals__
|
26天前
|
C语言
【数据结构】栈和队列（c语言实现）（附源码）
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表，遵循“先进后出”原则；队列则在一端插入、另一端删除，遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现，并提供了完整的代码示例。栈和队列在实际应用中非常广泛，如二叉树的层序遍历和快速排序的非递归实现等。
ephemerals__
122 9
进步`于辰
|
23天前
|
存储 算法 Java
散列表的数据结构以及对象在JVM堆中的存储过程
本文介绍了散列表的基本概念及其在JVM中的应用，详细讲解了散列表的结构、对象存储过程、Hashtable的扩容机制及与HashMap的区别。通过实例和图解，帮助读者理解散列表的工作原理和优化策略。
进步`于辰
30 1
散列表的数据结构以及对象在JVM堆中的存储过程
XIAZHI
|
2月前
|
存储 算法 C语言
通义灵码在考研C语言和数据结构中的应用实践 1-5
通义灵码在考研C语言和数据结构中的应用实践，体验通义灵码的强大思路。《趣学C语言和数据结构100例》精选了五个经典问题及其解决方案，包括求最大公约数和最小公倍数、统计字符类型、求特殊数列和、计算阶乘和双阶乘、以及求斐波那契数列的前20项和。通过这些实例，帮助读者掌握C语言的基本语法和常用算法，提升编程能力。
XIAZHI
69 4
ephemerals__
|
25天前
|
存储 搜索推荐 算法
【数据结构】树型结构详解 + 堆的实现（c语言）（附源码）
本文介绍了树和二叉树的基本概念及结构，重点讲解了堆这一重要的数据结构。堆是一种特殊的完全二叉树，常用于实现优先队列和高效的排序算法（如堆排序）。文章详细描述了堆的性质、存储方式及其实现方法，包括插入、删除和取堆顶数据等操作的具体实现。通过这些内容，读者可以全面了解堆的原理和应用。
ephemerals__
63 16
ephemerals__
|
25天前
|
C语言
【数据结构】二叉树（c语言）（附源码）
本文介绍了如何使用链式结构实现二叉树的基本功能，包括前序、中序、后序和层序遍历，统计节点个数和树的高度，查找节点，判断是否为完全二叉树，以及销毁二叉树。通过手动创建一棵二叉树，详细讲解了每个功能的实现方法和代码示例，帮助读者深入理解递归和数据结构的应用。
ephemerals__
82 8
ephemerals__
|
28天前
|
存储 C语言
【数据结构】手把手教你单链表（c语言）（附源码）
本文介绍了单链表的基本概念、结构定义及其实现方法。单链表是一种内存地址不连续但逻辑顺序连续的数据结构，每个节点包含数据域和指针域。文章详细讲解了单链表的常见操作，如头插、尾插、头删、尾删、查找、指定位置插入和删除等，并提供了完整的C语言代码示例。通过学习单链表，可以更好地理解数据结构的底层逻辑，提高编程能力。
ephemerals__
54 4
ephemerals__
|
29天前
|
存储 C语言
【数据结构】顺序表（c语言实现）（附源码）
本文介绍了线性表和顺序表的基本概念及其实现。线性表是一种有限序列，常见的线性表有顺序表、链表、栈、队列等。顺序表是一种基于连续内存地址存储数据的数据结构，其底层逻辑是数组。文章详细讲解了静态顺序表和动态顺序表的区别，并重点介绍了动态顺序表的实现，包括初始化、销毁、打印、增删查改等操作。最后，文章总结了顺序表的时间复杂度和局限性，并预告了后续关于链表的内容。
ephemerals__
60 3
初恋叫萱萱
|
29天前
|
存储 算法 C语言
C语言数据结构（2）
【10月更文挑战第21天】
初恋叫萱萱
33 2
XIAZHI
|
2月前
|
存储 算法 C语言
【趣学C语言和数据结构100例】
《趣学C语言和数据结构100例》精选5个编程问题，涵盖求最大公约数与最小公倍数、字符统计、特殊序列求和及阶乘计算等，通过实例讲解C语言基础与算法思维，适合初学者实践学习。
XIAZHI
78 1
神明木佑
|
2月前
|
存储 JavaScript 前端开发
为什么基础数据类型存放在栈中，而引用数据类型存放在堆中？
为什么基础数据类型存放在栈中，而引用数据类型存放在堆中？
神明木佑
72 1