数据结构入门(C语言版)二叉树的顺序结构及堆的概念及结构实现应用(下)

简介: 这里的向上调整函数就是指定一个元素与其父亲比较,如果孩子小于父亲,就交换常用于小堆的插入与堆排序。

向上调整(AdjustUp)


代码如下:


void AdjustUp(int* a, int child)
{
  assert(a);
  int parent = (child - 1) / 2;
  while (child > 0)
  {
    if (a[child] < a[parent])
    {
      Swap(&a[child], &a[parent]);
      child = parent;
      parent = (child - 1) / 2;
    }
    else
    {
      break;
    }
  }
}


这里的向上调整函数就是指定一个元素与其父亲比较,如果孩子小于父亲,就交换

常用于小堆的插入与堆排序。


向下调整(AdjustDown)


代码如下:


void AdjustDown(int* a, int n, int parent)
{
  int child = parent * 2 + 1;
  while (child < n)
  {
    // 选出左右孩子中小的那一个
    if (child + 1 < n && a[child + 1] < a[child])
    {
      ++child;
    }
    // 如果小的孩子小于父亲,则交换,并继续向下调整
    if (a[child] < a[parent])
    {
      Swap(&a[child], &a[parent]);
      parent = child;
      child = parent * 2 + 1;
    }
    else
    {
      break;
    }
  }
}


这里的向下调整函数就是指定一个元素与其父亲比较,如果孩子小于父亲,就交换

同样常用于小堆的插入与堆排序,和向上调整的不同的就是方向。


堆的初始化(HeapInit)


代码如下:


void HeapInit(HP* hp)
{
  assert(hp);
  hp->a = NULL;
  hp->size = hp->capacity = 0;
}


堆的销毁(HeapDestroy)


代码如下:


void HeapDestroy(HP* hp)
{
  assert(hp);
  free(hp->a);
  hp->capacity = hp->size = 0;
}


堆的插入(HeapPush)


代码如下:


void HeapPush(HP* hp, HPDataType x)
{
  assert(hp);
  if (hp->size == hp->capacity)
  {
    size_t newCapacity = hp->capacity == 0 ? 4 : hp->capacity * 2;
    HPDataType* tmp = realloc(hp->a, sizeof(HPDataType)*newCapacity);
    if (tmp == NULL)
    {
      printf("realloc fail\n");
      exit(-1);
    }
    hp->a = tmp;
    hp->capacity = newCapacity;
  }
  hp->a[hp->size] = x;
  hp->size++;
  AdjustUp(hp->a, hp->size - 1);
}


堆的插入,首先创建内存空间,然后插入元素,size++就不说了;

重点讲一下这里的向上调整,因为是小数往上调,所以这里的调用是用于小堆的建立;

如果要改成大堆,那么就要将向上调整函数的判断改为大于;

修改后代码如下:


if (a[child] >  a[parent])


堆的删除(HeapPop)


代码如下:


void HeapPop(HP* hp)
{
  assert(hp);
  assert(!HeapEmpty(hp));
  Swap(&hp->a[0], &hp->a[hp->size - 1]);
  hp->size--;
  AdjustDown(hp->a, hp->size, 0);
}


堆的删除是删除堆顶的元素,但是需要注意的是并不是直接将堆顶元素直接删除

而是将堆顶元素和最后一个元素交换,再进行size–

再将换上去的最后的元素重新向下调整到相应位置

这样做的目的是为了保持堆的基本结构,否则可能堆结构可能不成立。


取堆顶的数据(HeapTop)


代码如下:


HPDataType HeapTop(HP* hp)
{
  assert(hp);
  assert(!HeapEmpty(hp));
  return hp->a[0];
}


直接返回第一个元素即可


堆的打印(HeapPrint)


代码如下:


void HeapPrint(HP* hp)
{
  for (int i = 0; i < hp->size; ++i)
  {
    printf("%d ", hp->a[i]);
  }
  printf("\n");
}


常用的for循环对顺序表进行元素遍历逐个打印


堆的判空(HeapEmpty)


代码如下:


bool HeapEmpty(HP* hp)
{
  assert(hp);
  return hp->size == 0;
}


这里使用的是bool值,当然你也可以使用int类型


堆的数据个数(HeapSize)


代码如下:


int HeapSize(HP* hp)
{
  assert(hp);
  return hp->size;
}


堆排序的简易例子


代码如下:


void HeapSort(int* a, int n)
{
  for (int i = (n - 1 - 1) / 2; i >= 0; --i)
  {
    AdjustDown(a, n, i);
  }
  for (int end = n - 1; end > 0; --end)
  {
    Swap(&a[end], &a[0]);
    AdjustDown(a, end, 0);
  }
}
int main()
{
  int a[] = { 70, 56, 30, 25, 15, 10, 75, 33, 50, 69 };
  HeapSort(a, sizeof(a) / sizeof(a[0]));
  for (int i = 0; i < sizeof(a) / sizeof(a[0]); ++i)
  {
    printf("%d ", a[i]);
  }
  printf("\n");
  return 0;
}


这里我们主要使用向下调整的方法来实现,因为上面对堆的删除是用于小堆

所以这里调用向下调整后,该数组为降序,排序后打印如下:


75 70 69 56 50 33 30 25 15 10


如果要进行升序排序,我们只需将向下调整函数的部分符号修改即可

修改如下:


void AdjustDown(int* a, int n, int parent)
{
  int child = parent * 2 + 1;
  while (child < n)
  {
    if (child + 1 < n && a[child + 1] > a[child])
    {
      ++child;
    }
    if (a[child] > a[parent])
    {
      Swap(&a[child], &a[parent]);
      parent = child;
      child = parent * 2 + 1;
    }
    else
    {
      break;
    }
  }
}


排序后打印如下:


10 15 25 30 33 50 56 69 70 75


结语


有兴趣的小伙伴可以关注作者,如果觉得内容不错,请给个一键三连吧,蟹蟹你哟!!!

制作不易,如有不正之处敬请指出

感谢大家的来访,UU们的观看是我坚持下去的动力

在时间的催化剂下,让我们彼此都成为更优秀的人吧!!!


b9c82e0041614632bd01498e5ec4cd2b.png

相关文章
|
18天前
|
存储 算法
数据结构与算法学习二二:图的学习、图的概念、图的深度和广度优先遍历
这篇文章详细介绍了图的概念、表示方式以及深度优先遍历和广度优先遍历的算法实现。
32 1
数据结构与算法学习二二:图的学习、图的概念、图的深度和广度优先遍历
|
17天前
|
存储 JavaScript 前端开发
为什么基础数据类型存放在栈中,而引用数据类型存放在堆中?
为什么基础数据类型存放在栈中,而引用数据类型存放在堆中?
53 1
|
21天前
|
分布式计算 Hadoop Unix
Hadoop-28 ZooKeeper集群 ZNode简介概念和测试 数据结构与监听机制 持久性节点 持久顺序节点 事务ID Watcher机制
Hadoop-28 ZooKeeper集群 ZNode简介概念和测试 数据结构与监听机制 持久性节点 持久顺序节点 事务ID Watcher机制
39 1
|
18天前
|
存储 算法
探索数据结构:分支的世界之二叉树与堆
探索数据结构:分支的世界之二叉树与堆
|
18天前
探索顺序结构:栈的实现方式
探索顺序结构:栈的实现方式
|
20天前
|
存储 算法 Java
【用Java学习数据结构系列】用堆实现优先级队列
【用Java学习数据结构系列】用堆实现优先级队列
28 0
|
20天前
|
存储 分布式计算 算法
大数据-105 Spark GraphX 基本概述 与 架构基础 概念详解 核心数据结构
大数据-105 Spark GraphX 基本概述 与 架构基础 概念详解 核心数据结构
32 0
|
22天前
|
存储 算法
【数据结构】二叉树——顺序结构——堆及其实现
【数据结构】二叉树——顺序结构——堆及其实现
|
18天前
|
算法 程序员 索引
数据结构与算法学习七:栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
栈的基本概念、应用场景以及如何使用数组和单链表模拟栈,并展示了如何利用栈和中缀表达式实现一个综合计算器。
18 1
数据结构与算法学习七:栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
|
18天前
初步认识栈和队列
初步认识栈和队列
44 10