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

简介: <堆及堆排序>《数据结构(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 作者:新晓·故知

相关文章
|
1月前
|
机器学习/深度学习 算法 C语言
【趣学C语言和数据结构100例】11-15
本文介绍了五个C语言编程问题及其实现,包括矩阵对角线元素之和、有序数组插入、数组逆序、杨辉三角输出和魔方阵生成。每个问题不仅涉及基本的数组操作,还涵盖了算法设计的核心思想,如循环、条件判断和递归。通过解决这些问题,读者可以加深对C语言和数据结构的理解,提升编程技能。这些问题的解决过程展示了如何有效处理数组和矩阵,以及如何利用算法优化程序性能,为实际应用提供了宝贵的实践经验。
60 4
【趣学C语言和数据结构100例】11-15
|
27天前
|
算法 数据处理 C语言
C语言中的位运算技巧,涵盖基本概念、应用场景、实用技巧及示例代码,并讨论了位运算的性能优势及其与其他数据结构和算法的结合
本文深入解析了C语言中的位运算技巧,涵盖基本概念、应用场景、实用技巧及示例代码,并讨论了位运算的性能优势及其与其他数据结构和算法的结合,旨在帮助读者掌握这一高效的数据处理方法。
45 1
|
1月前
|
存储 算法 搜索推荐
【趣学C语言和数据结构100例】91-95
本文涵盖多个经典算法问题的C语言实现,包括堆排序、归并排序、从长整型变量中提取偶数位数、工人信息排序及无向图是否为树的判断。通过这些问题,读者可以深入了解排序算法、数据处理方法和图论基础知识,提升编程能力和算法理解。
49 4
|
1月前
|
存储 机器学习/深度学习 搜索推荐
【趣学C语言和数据结构100例】86-90
本文介绍并用C语言实现了五种经典排序算法:直接插入排序、折半插入排序、冒泡排序、快速排序和简单选择排序。每种算法都有其特点和适用场景,如直接插入排序适合小规模或基本有序的数据,快速排序则适用于大规模数据集,具有较高的效率。通过学习这些算法,读者可以加深对数据结构和算法设计的理解,提升解决实际问题的能力。
45 4
|
1月前
|
存储 算法 数据处理
【趣学C语言和数据结构100例】81-85
本文介绍了五个经典算法问题及其C语言实现,涵盖图论与树结构的基础知识。包括使用BFS求解单源最短路径、统计有向图中入度或出度为0的点数、统计无向无权图各顶点的度、折半查找及二叉排序树的查找。这些算法不仅理论意义重大,且在实际应用中极为广泛,有助于提升编程能力和数据结构理解。
44 4
|
1月前
|
算法 数据可视化 数据建模
【趣学C语言和数据结构100例】76-80
本文介绍了五种图论算法的C语言实现,涵盖二叉树的层次遍历及广度优先搜索(BFS)和深度优先搜索(DFS)的邻接表与邻接矩阵实现。层次遍历使用队列按层访问二叉树节点;BFS利用队列从源节点逐层遍历图节点,适用于最短路径等问题;DFS通过递归或栈深入图的分支,适合拓扑排序等场景。这些算法是数据结构和算法学习的基础,对提升编程能力和解决实际问题至关重要。
52 4
|
1月前
|
存储 算法 vr&ar
【趣学C语言和数据结构100例】71-75
本文介绍了五个C语言数据结构问题及其实现,涵盖链表与二叉树操作,包括按奇偶分解链表、交换二叉树左右子树、查找节点的双亲节点、计算二叉树深度及求最大关键值。通过递归和遍历等方法,解决了理论与实际应用中的常见问题,有助于提升编程能力和数据结构理解。
43 4
|
1月前
|
存储 算法 C语言
【趣学C语言和数据结构100例】66-70
本书《趣学C语言和数据结构100例》精选了5个典型的数据结构问题及C语言实现,涵盖链表与数组操作,如有序集合的集合运算、有序序列表的合并、数组中两顺序表位置互换、三递增序列公共元素查找及奇偶数重排。通过详细解析与代码示例,帮助读者深入理解数据结构与算法设计的核心思想,提升编程技能。
36 4
|
1月前
|
存储 算法 C语言
【趣学C语言和数据结构100例】51-55
本文介绍了五个关于链表操作的C语言实现案例,包括删除单链表中的重复元素、从两个有序链表中查找公共元素、判断一个链表是否为另一链表的连续子序列、判断循环双链表是否对称及合并两个循环单链表。每个案例都详细解析了算法思路与实现方法,涵盖了链表操作的多种场景,旨在帮助读者深入理解链表数据结构的应用,提升算法设计与编程能力。
43 4
|
1月前
|
存储 算法 C语言
【趣学C语言和数据结构100例】16-20
本文精选了五个C语言编程问题,涵盖数组操作、字符串处理等基础领域。包括查找二维数组中的鞍点、折半查找法、统计文章中字符数量、电文解密及字符串连接。每个问题都附有详细的代码实现与分析,旨在帮助读者理解算法逻辑,提升编程技巧。通过这些实践,不仅能锻炼编程能力,还能加深对数据结构和算法的理解,为未来的学习和工作打下坚实基础。
66 4