【数据结构入门】-堆的实现以及堆排序(2)

简介: 【数据结构入门】-堆的实现以及堆排序(2)


堆排序

前面我们已经实现了堆的实现,其中堆的实现中最重要的算法就是向上调整和向下调整了。接下来的堆排序也同样的跟这两种算法息息相关。所以向上调整和向下调整这两种算法一定要好好掌握。

在学习堆排序之前我们先来思考一个问题,既然是堆排序,那么我们在对数据进行排序的时候是否真的需要一个堆呢?是否真的需要先提前把这个堆的数据结构实现完成之后才能实现堆排序这个算法呢?

如果真是这样的话那岂不是太麻烦了。所以我们不需要提前实现好堆,我们可以处理数组中的元素使这个数组中的元素变成一个堆。大家不要忘记了,堆是在完全二叉树的基础上增加了一个限制条件,这个限制条件就是堆的某个结点总是不大于或者不小于其父结点的值;另外这个堆底层就是用数组来实现的。

我们在实现堆排序的时候可以把这个数组想象成一个完全二叉树,然后通过一定的算法实现把这个完全二叉树搞成一个堆。我们通常把这个过程叫做建堆。

好了,实现堆排序的第一步就是把数组中的数据搞成一个堆,即我们必须先实现建堆的算法。而建堆有两种方法来实现,一种是向上调整法,另一种就是向下调整法。


建堆

向上调整法建堆

通过利用我们刚刚实现堆的向上调整的算法来建堆(不要把这个算法想象的那么高深莫测,其实就是我们对这个数组进行一定的算法实现使这个数组中的元素变成堆的数据结构),最终结果是建立一个大根堆。

我们直接看最关键的向上调整法的代码:

void AdjustUp(int* a, int child)
{
  //父亲就是(孩子-1)/2
  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;
  }
  }
}


此时,我们就会得到一个数组,这个数组中的元素就是一个大根堆的结构。

这个过程就是模拟插入建堆(操控的数组的数据,而不是堆中的数据)。

举个例子吧:

6.png

这个数组经过向上调整法之后就变成了这样:7.png

如果想要得到一个小根堆的话,只需要把向上调整法中a[child] > a[parent]的>改为<就可以了,即a[child] < a[parent]。程序运行之后就是:

8.png

所以这里得到的就是一个小根堆。


向下调整法建堆

//向下调整建堆
  for (int i = (n - 1 - 1) / 2; i >= 0; i--)
  {
  AdjustDown2(a, n, i);
  }

9.png

利用堆删除的思想来进行排序

刚刚通过向上调整法已经建立了大堆或者小堆,接下来就开始进行排序了。对于排序的话,无非就是升序和降序。

结论就是:升序用大堆,降序就用小堆。

我们先来看升序的过程(总共有两个步骤):

第一步就是先利用向上调整建立一个大堆,第二步就是利用堆删除的思想来排序,最终就会得到一个升序的数组。

这里我简单说一下第二个步骤(利用向下调整来进行实现):我们通过第一步建立了一个大堆,接下来开始第二步:让堆顶和堆尾进行交换,然后对此时的堆顶进行向下调整,接着交换堆顶和堆中倒数第二个数据,再次对此时堆顶的数据进行向下调整;重复此过程。最终就可以得到一个升序的数组。

下面是升序过程中最核心的代码:

void AdjustUp(int* a, int child)
{
  //父亲就是(孩子-1)/2
  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;
  }
  }
}
void AdjustDown2(int* a, int n, int parent)
{
  int child = parent * 2 + 1;
  while (child < n)
  {
  if (child + 1 < n && a[child] < a[child + 1])
  {
    child++;
  }
  if (a[child] > a[parent])
  {
    swap(&a[child], &a[parent]);
    parent = child;
    child = parent * 2 + 1;
  }
  else
  {
    break;
  }
  }
}
void HeapSort(int* a, int n)
{
  for (int i = 1; i < n; i++)
  {
  AdjustUp(a, i);
  }
  int end = n - 1;
  while (end > 0)
  {
  swap(&a[end], &a[0]);
  //AdjustDown1(a, end, 0);
  AdjustDown2(a, end, 0);
  end--;
  }
}

1.gif

上图就是整个升序的过程:先利用向上调整来建立一个大堆,然后利用向下调整进行升序排序(第二个过程其实就是一个堆删除的思想)。


升序代码

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
void swap(int* p1, int* p2)
{
  int tmp = *p1;
  *p1 = *p2;
  *p2 = tmp;
}
void AdjustUp(int* a, int child)
{
  //父亲就是(孩子-1)/2
  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;
  }
  }
}
void AdjustDown2(int* a, int n, int parent)
{
  int child = parent * 2 + 1;
  while (child < n)
  {
  if (child + 1 < n && a[child] < a[child + 1])
  {
    child++;
  }
  if (a[child] > a[parent])
  {
    swap(&a[child], &a[parent]);
    parent = child;
    child = parent * 2 + 1;
  }
  else
  {
    break;
  }
  }
}
void HeapSort(int* a, int n)
{
  for (int i = 1; i < n; i++)
  {
  AdjustUp(a, i);
  }
  int end = n - 1;
  while (end > 0)
  {
  swap(&a[end], &a[0]);
  //AdjustDown1(a, end, 0);
  AdjustDown2(a, end, 0);
  end--;
  }
}
int main()
{
  int a[10] = { 8,5,2,1,4,7,9,6,3,10 };
  HeapSort(a, 10);
  for (int i = 0; i < 10; i++)
  {
  printf("%d ", a[i]);
  }
  return 0;
}

10.png

降序代码

其实降序和升序的思路可以说基本上就是一模一样的。


#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
void swap(int* p1, int* p2)
{
  int tmp = *p1;
  *p1 = *p2;
  *p2 = tmp;
}
void AdjustUp(int* a, int child)
{
  //父亲就是(孩子-1)/2
  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;
  }
  }
}
//向下调整,基础为小堆
void AdjustDown1(int* a, int n, int parent)
{
  int child = parent * 2 + 2;
  while (child < n)
  {
  if (child < n && a[child - 1] < a[child])
  {
    child--;
  }
  if (a[child] < a[parent])
  {
    swap(&a[child], &a[parent]);
    parent = child;
    child = parent * 2 + 2;
  }
  else
  {
    break;
  }
  }
}
//向下调整,基础为大堆
void AdjustDown2(int* a, int n, int parent)
{
  int child = parent * 2 + 1;
  while (child < n)
  {
  if (child + 1 < n && a[child] < a[child + 1])
  {
    child++;
  }
  if (a[child] > a[parent])
  {
    swap(&a[child], &a[parent]);
    parent = child;
    child = parent * 2 + 1;
  }
  else
  {
    break;
  }
  }
}
void HeapSort(int* a, int n)
{
  //向上调整建堆
  for (int i = 1; i < n; i++)
  {
  AdjustUp(a, i);
  }
  向下调整建堆
  //for (int i = (n - 1 - 1) / 2; i >= 0; i--)
  //{
  //  AdjustDown1(a, n, i);
  //}
  int end = n - 1;
  while (end > 0)
  {
  swap(&a[end], &a[0]);
  AdjustDown1(a, end, 0);
  //AdjustDown2(a, end, 0);
  end--;
  }
}
int main()
{
  int a[10] = { 8,5,2,1,4,7,9,6,3,10 };
  HeapSort(a, 10);
  for (int i = 0; i < 10; i++)
  {
  printf("%d ", a[i]);
  }
  return 0;
}

11.png

好了,以上就是这篇文章的全部内容了,说实话,不简单,这需要我们不断的理解才可以把着块的内容吃透。

诸位一起加油吧!!!就到这里,再见啦,各位

目录
相关文章
|
20天前
|
存储 JavaScript 前端开发
为什么基础数据类型存放在栈中,而引用数据类型存放在堆中?
为什么基础数据类型存放在栈中,而引用数据类型存放在堆中?
60 1
|
22天前
|
算法 搜索推荐
数据结构与算法学习十八:堆排序
这篇文章介绍了堆排序是一种通过构建堆数据结构来实现的高效排序算法,具有平均和最坏时间复杂度为O(nlogn)的特点。
59 0
数据结构与算法学习十八:堆排序
|
21天前
|
存储 算法
探索数据结构:分支的世界之二叉树与堆
探索数据结构:分支的世界之二叉树与堆
|
21天前
|
存储 机器学习/深度学习 算法
探索数据结构:入门及复杂度的解锁
探索数据结构:入门及复杂度的解锁
|
23天前
|
存储 算法 Java
【用Java学习数据结构系列】用堆实现优先级队列
【用Java学习数据结构系列】用堆实现优先级队列
28 0
|
25天前
|
存储 算法
【数据结构】二叉树——顺序结构——堆及其实现
【数据结构】二叉树——顺序结构——堆及其实现
|
27天前
【数据结构】大根堆和小根堆
【数据结构】大根堆和小根堆
20 0
|
27天前
|
存储 缓存 应用服务中间件
Nginx入门 -- 基本数据结构中之ngx_hash_t
Nginx入门 -- 基本数据结构中之ngx_hash_t
34 0
|
22天前
|
算法 程序员 索引
数据结构与算法学习七:栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
栈的基本概念、应用场景以及如何使用数组和单链表模拟栈,并展示了如何利用栈和中缀表达式实现一个综合计算器。
18 1
数据结构与算法学习七:栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
|
2天前
|
算法 安全 NoSQL
2024重生之回溯数据结构与算法系列学习之栈和队列精题汇总(10)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第3章之IKUN和I原达人之数据结构与算法系列学习栈与队列精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!