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

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

2022-11-27 169
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： ＜堆及堆排序＞《数据结构(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语言数据结构
堆数据结构
数据结构堆排序
堆排序数据结构
新晓故知
目录
相关文章
aliyun3611036241
|
12天前
|
存储 算法 C语言
通义灵码在考研C语言和数据结构中的应用实践 1-5
通义灵码在考研C语言和数据结构中的应用实践，体验通义灵码的强大思路。《趣学C语言和数据结构100例》精选了五个经典问题及其解决方案，包括求最大公约数和最小公倍数、统计字符类型、求特殊数列和、计算阶乘和双阶乘、以及求斐波那契数列的前20项和。通过这些实例，帮助读者掌握C语言的基本语法和常用算法，提升编程能力。
aliyun3611036241
49 4
ephemerals__
|
23小时前
|
存储 C语言
【数据结构】顺序表（c语言实现）（附源码）
本文介绍了线性表和顺序表的基本概念及其实现。线性表是一种有限序列，常见的线性表有顺序表、链表、栈、队列等。顺序表是一种基于连续内存地址存储数据的数据结构，其底层逻辑是数组。文章详细讲解了静态顺序表和动态顺序表的区别，并重点介绍了动态顺序表的实现，包括初始化、销毁、打印、增删查改等操作。最后，文章总结了顺序表的时间复杂度和局限性，并预告了后续关于链表的内容。
ephemerals__
10 3
aliyun1622584902-46568
|
1天前
|
存储 算法 C语言
C语言数据结构（2）
【10月更文挑战第21天】
aliyun1622584902-46568
6 2
aliyun3611036241
|
12天前
|
存储 算法 C语言
【趣学C语言和数据结构100例】
《趣学C语言和数据结构100例》精选5个编程问题，涵盖求最大公约数与最小公倍数、字符统计、特殊序列求和及阶乘计算等，通过实例讲解C语言基础与算法思维，适合初学者实践学习。
aliyun3611036241
59 1
神明木佑
|
18天前
|
存储 JavaScript 前端开发
为什么基础数据类型存放在栈中，而引用数据类型存放在堆中？
为什么基础数据类型存放在栈中，而引用数据类型存放在堆中？
神明木佑
54 1
java冯坚持
|
19天前
|
算法 搜索推荐
数据结构与算法学习十八：堆排序
这篇文章介绍了堆排序是一种通过构建堆数据结构来实现的高效排序算法，具有平均和最坏时间复杂度为O(nlogn)的特点。
java冯坚持
59 0
数据结构与算法学习十八：堆排序
GuGuStudy
|
21天前
|
存储 C语言
探索C语言数据结构：利用顺序表完成通讯录的实现
本文介绍了如何使用C语言中的顺序表数据结构实现一个简单的通讯录，包括初始化、添加、删除、查找和保存联系人信息的操作，以及自定义结构体用于存储联系人详细信息。
GuGuStudy
18 2
2的n次方_
|
2月前
|
存储 Java
【数据结构】优先级队列（堆）从实现到应用详解
本文介绍了优先级队列的概念及其底层数据结构——堆。优先级队列根据元素的优先级而非插入顺序进行出队操作。JDK1.8中的`PriorityQueue`使用堆实现，堆分为大根堆和小根堆。大根堆中每个节点的值都不小于其子节点的值，小根堆则相反。文章详细讲解了如何通过数组模拟实现堆，并提供了创建、插入、删除以及获取堆顶元素的具体步骤。此外，还介绍了堆排序及解决Top K问题的应用，并展示了Java中`PriorityQueue`的基本用法和注意事项。
2的n次方_
41 5
【数据结构】优先级队列（堆）从实现到应用详解
平凡程序猿~
|
26天前
|
存储 算法 调度
数据结构--二叉树的顺序实现（堆实现）
数据结构--二叉树的顺序实现（堆实现）
平凡程序猿~
48 1
是店小二呀
|
27天前
|
存储 算法 分布式数据库
【初阶数据结构】理解堆的特性与应用：深入探索完全二叉树的独特魅力
【初阶数据结构】理解堆的特性与应用：深入探索完全二叉树的独特魅力
是店小二呀
27 1

热门文章

最新文章

  • 1
    C语言编程入门之--第四章C语言基本数据类型
  • 2
    【C语言】学习笔记4——数组
  • 3
    C语言OJ项目参考(1034) 求值
  • 4
    C# Json处理日期和Table
  • 5
    算法学习之C语言基础
  • 6
    C语言中的逗号操作符
  • 7
    c语言中常见错误总结
  • 8
    【C语言进阶】文件操作（一）
  • 9
    进阶C语言——指针【详解】（一）
  • 10
    LeetCode刷题(9)【树】前序&深度&平衡(C语言)
  • 1
    【MongoDB】MongoDB 如何处理复杂的数据结构？
    128
  • 2
    【数据结构】排序算法
    45
  • 3
    【数据结构】C语言实现链队列(附完整运行代码)
    120
  • 4
    深入理解InnoDB索引数据结构和算法
    311
  • 5
    【数据结构】深入浅出理解链表中二级指针的应用
    99
  • 6
    【数据结构】线性表的链式存储结构
    65
  • 7
    【数据结构】C语言实现顺序表万字详解(附完整运行代码)
    147
  • 8
    【Redis技术进阶之路】「底层源码解析」揭秘高效存储模型与数据结构底层实现（字典）（二）
    112
  • 9
    作者推荐 |【Redis技术进阶之路】「原理系列开篇」揭秘高效存储模型与数据结构底层实现（SDS）（三）
    76
  • 10
    金石推荐 | 【算法数据结构专题】「延时队列算法」史上手把手教你针对层级时间轮（TimingWheel）实现延时队列的开发实战落地（下）（一）
    125

    • 相关课程

    更多
  • Go语言核心编程 - 数据结构和算法
  • 你的第一门C语言课
  • C语言学习教程
  • Go语言核心编程 - 基础语法、数组、切片、Map

    • 相关电子书

    更多
  • 如何使用Tair增强数据结构构建丰富在线实时场景
  • Apache Flink 流式应用中状态的数据结构定义升级
  • 低代码开发师（初级）实战教程
    • 下一篇
    阿里云无影云电脑免费试用，最长可试用3个月