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

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

2022-11-27 166
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： ＜堆及堆排序＞《数据结构(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语言数据结构
堆数据结构
数据结构堆排序
堆排序数据结构
新晓故知
目录
相关文章
土木林森
|
23天前
|
存储 算法 C语言
"揭秘C语言中的王者之树——红黑树：一场数据结构与算法的华丽舞蹈，让你的程序效率飙升，直击性能巅峰！"
【8月更文挑战第20天】红黑树是自平衡二叉查找树，通过旋转和重着色保持平衡，确保高效执行插入、删除和查找操作，时间复杂度为O(log n)。本文介绍红黑树的基本属性、存储结构及其C语言实现。红黑树遵循五项基本规则以保持平衡状态。在C语言中，节点包含数据、颜色、父节点和子节点指针。文章提供了一个示例代码框架，用于创建节点、插入节点并执行必要的修复操作以维护红黑树的特性。
土木林森
45 1
小徐在进步
|
2天前
|
存储 算法 C语言
数据结构基础详解(C语言): 二叉树的遍历_线索二叉树_树的存储结构_树与森林详解
本文从二叉树遍历入手，详细介绍了先序、中序和后序遍历方法，并探讨了如何构建二叉树及线索二叉树的概念。接着，文章讲解了树和森林的存储结构，特别是如何将树与森林转换为二叉树形式，以便利用二叉树的遍历方法。最后，讨论了树和森林的遍历算法，包括先根、后根和层次遍历。通过这些内容，读者可以全面了解二叉树及其相关概念。
小徐在进步
22 6
小徐在进步
|
2天前
|
存储 算法 C语言
数据结构基础详解(C语言):单链表_定义_初始化_插入_删除_查找_建立操作_纯c语言代码注释讲解
本文详细介绍了单链表的理论知识，涵盖单链表的定义、优点与缺点，并通过示例代码讲解了单链表的初始化、插入、删除、查找等核心操作。文中还具体分析了按位序插入、指定节点前后插入、按位序删除及按值查找等算法实现，并提供了尾插法和头插法建立单链表的方法，帮助读者深入理解单链表的基本原理与应用技巧。
小徐在进步
21 6
小徐在进步
|
2天前
|
存储 C语言 C++
数据结构基础详解(C语言) 顺序表：顺序表静态分配和动态分配增删改查基本操作的基本介绍及c语言代码实现
本文介绍了顺序表的定义及其在C/C++中的实现方法。顺序表通过连续存储空间实现线性表，使逻辑上相邻的元素在物理位置上也相邻。文章详细描述了静态分配与动态分配两种方式下的顺序表定义、初始化、插入、删除、查找等基本操作，并提供了具体代码示例。静态分配方式下顺序表的长度固定，而动态分配则可根据需求调整大小。此外，还总结了顺序表的优点，如随机访问效率高、存储密度大，以及缺点，如扩展不便和插入删除操作成本高等特点。
小徐在进步
16 5
小徐在进步
|
2天前
|
存储 机器学习/深度学习 C语言
数据结构基础详解(C语言): 树与二叉树的基本类型与存储结构详解
本文介绍了树和二叉树的基本概念及性质。树是由节点组成的层次结构，其中节点的度为其分支数量，树的度为树中最大节点度数。二叉树是一种特殊的树，其节点最多有两个子节点，具有多种性质，如叶子节点数与度为2的节点数之间的关系。此外，还介绍了二叉树的不同形态，包括满二叉树、完全二叉树、二叉排序树和平衡二叉树，并探讨了二叉树的顺序存储和链式存储结构。
小徐在进步
10 3
小徐在进步
|
2天前
|
存储 C语言
数据结构基础详解(C语言): 栈与队列的详解附完整代码
栈是一种仅允许在一端进行插入和删除操作的线性表，常用于解决括号匹配、函数调用等问题。栈分为顺序栈和链栈，顺序栈使用数组存储，链栈基于单链表实现。栈的主要操作包括初始化、销毁、入栈、出栈等。栈的应用广泛，如表达式求值、递归等场景。栈的顺序存储结构由数组和栈顶指针构成，链栈则基于单链表的头插法实现。
小徐在进步
14 3
小徐在进步
|
2天前
|
存储 C语言
数据结构基础详解(C语言): 树与二叉树的应用_哈夫曼树与哈夫曼曼编码_并查集_二叉排序树_平衡二叉树
本文详细介绍了树与二叉树的应用，涵盖哈夫曼树与哈夫曼编码、并查集以及二叉排序树等内容。首先讲解了哈夫曼树的构造方法及其在数据压缩中的应用；接着介绍了并查集的基本概念、存储结构及优化方法；随后探讨了二叉排序树的定义、查找、插入和删除操作；最后阐述了平衡二叉树的概念及其在保证树平衡状态下的插入和删除操作。通过本文，读者可以全面了解树与二叉树在实际问题中的应用技巧和优化策略。
小徐在进步
12 2
小徐在进步
|
2天前
|
存储 算法 C语言
C语言手撕数据结构代码_顺序表_静态存储_动态存储
本文介绍了基于静态和动态存储的顺序表操作实现，涵盖创建、删除、插入、合并、求交集与差集、逆置及循环移动等常见操作。通过详细的C语言代码示例，展示了如何高效地处理顺序表数据结构的各种问题。
小徐在进步
10 1
小徐在进步
|
22小时前
|
存储 人工智能 C语言
数据结构基础详解(C语言): 栈的括号匹配(实战)与栈的表达式求值&&特殊矩阵的压缩存储
本文首先介绍了栈的应用之一——括号匹配，利用栈的特性实现左右括号的匹配检测。接着详细描述了南京理工大学的一道编程题，要求判断输入字符串中的括号是否正确匹配，并给出了完整的代码示例。此外，还探讨了栈在表达式求值中的应用，包括中缀、后缀和前缀表达式的转换与计算方法。最后，文章介绍了矩阵的压缩存储技术，涵盖对称矩阵、三角矩阵及稀疏矩阵的不同压缩存储策略，提高存储效率。
小徐在进步
15 8
小徐在进步
|
22小时前
|
C语言
数据结构基础详解(C语言):图的基本概念_无向图_有向图_子图_生成树_生成森林_完全图
本文介绍了图的基本概念，包括图的定义、无向图与有向图、简单图与多重图等，并解释了顶点度、路径、连通性等相关术语。此外还讨论了子图、生成树、带权图及几种特殊形态的图，如完全图和树等。通过这些概念，读者可以更好地理解图论的基础知识。
小徐在进步
16 8