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

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

2022-11-27 156
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： ＜堆及堆排序＞《数据结构(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语言
数据结构堆排序
堆排序数据结构
新晓故知
目录
相关文章
泥腿子架构师
|
1天前
|
存储 缓存 算法
堆和栈的区别及应用场景
堆和栈的区别及应用场景
泥腿子架构师
16 2
jjczqyjxgdegi
|
5天前
|
存储 人工智能 程序员
技术心得记录：堆(heap)与栈(stack)的区别
技术心得记录：堆(heap)与栈(stack)的区别
jjczqyjxgdegi
5 0
米诺斯
|
5天前
|
存储 编译器 C语言
C语言的联合体：一种节省内存的数据结构
C语言的联合体：一种节省内存的数据结构
米诺斯
9 0
weixin_836869520
|
5天前
|
算法 搜索推荐 Java
Java数据结构与算法：排序算法之堆排序
Java数据结构与算法：排序算法之堆排序
weixin_836869520
7 0
反季雪
|
7天前
|
存储 算法 搜索推荐
【数据结构和算法】--- 基于c语言排序算法的实现（2）
【数据结构和算法】--- 基于c语言排序算法的实现（2）
反季雪
6 0
倔强的石头_
|
7天前
|
存储 缓存 前端开发
【数据结构/C语言】深入理解 双向链表
【数据结构/C语言】深入理解 双向链表
倔强的石头_
17 0
反季雪
|
7天前
|
搜索推荐 算法 C语言
【数据结构和算法】--- 基于c语言排序算法的实现（1）
【数据结构和算法】--- 基于c语言排序算法的实现（1）
反季雪
14 0
反季雪
|
7天前
|
存储 算法
【数据结构和算法】---二叉树（2）--堆的实现和应用
【数据结构和算法】---二叉树（2）--堆的实现和应用
反季雪
7 0
lge101058
|
7天前
|
存储 测试技术
【数据结构】详解堆的实现
【数据结构】详解堆的实现
lge101058
14 4
小森ai小小贾
|
11天前
|
算法 Python
数据结构算法--4堆排序
堆排序过程概述：建立大根堆，将堆顶最大元素移出并替换为末尾元素，调整保持堆性质，重复此过程直至堆为空，实现排序。时间复杂度为O(nlogn)。Python中可用heapq模块进行堆操作。
小森ai小小贾
20 3