目录
- 基本数据结构
- 堆排序
- 资料
- 收获
前面我们学习实践了冒泡排序和快速排序，这篇我们继续学习另外一种排序算法：堆排序，为了搞清楚什么是堆排序，我们需要先了解二叉树和堆，下面开始本篇的学习实践。
一、基本数据结构
数组，在内存中顺序存储
链表：分为单向链表、双向链表、双向循环链表。在内存中的存储方式是随机存储的。
数组和链表都属于线性的数据结构，其中数组在查找上效率高，而链表在插入、删除上效率高。数组和链表都是在数据存储的物理结构，即内存中存储的方式。
而队列、栈、树、图这些是为了更好的进行理解和编程而抽象出来的逻辑机构。
逻辑结构是抽象的，它依赖于物理结构而存在
图片来源于《漫画算法》
树：非线形的逻辑结构
在数据结构中，树的定位为：
树是n个节点的有限集，当n=0时，成为空树，在任意一个非空树中，又如下特种
- 有切仅有一个特定的根节点
- 当n>1 时，其余节点可分为m个互不相交的有限集，每一个集合本身又是一个树，成为根的子树。
二叉树
二叉树是一种特殊的树，每个节点最多有两个孩子节点。
二叉树可以用数组或者链表来存储。
图片是对《漫画算法》截图的编辑
可以分为 满二叉树、完全二叉树等
图片是对《漫画算法》截图的编辑
从解决“一边超级多另外一边很少”的自平衡问题的角度不同方式上，又有 红黑树的概念
二叉堆
二叉堆本质上是一种完全二叉树，它的存储方式不是链式结构，而是顺序存储即以数组形式。
分为两种类型：最大堆和最小堆
最大堆(大顶堆)：任何一个父节点的值，都大于等于它的孩子节点的值，即 堆顶是堆中最大的元素。
最小堆（小顶堆）：任何一个父节点的值，都小于等于它的孩子节点的值，即 堆顶是堆中最小的元素。
当插入、删除一个新的节点是，二叉堆会根据类型自动调整节点位置。
二叉堆是是实现堆排序和优先排序的基础
二、堆排序
通过上一小节，我们对数据结构的基本了解，了解了堆的结构以及存储方式。我们可以利用用二叉堆的排序以及自动调整节点位置的特性来实现排序。
如果想使用二叉堆来实现排序，有以下两步
- 把无序的数组构建成二叉堆（我们这里构建一个大顶堆，给下一步从小到大排序做好基础）
- 循环交换堆顶元素和二叉堆的尾端，砍断最后一个子节点（可理解为堆的个数减少一个），再次调整堆产生新的大顶堆。
如果遇到一个无序的完全二叉树，想变成堆，从depth-1层开始向上来实现
这里使用数组来表示一个完全二叉树，这样可以从任意节点拿到它的父节点 和它的左右子节点
如果子节点的下标是i，通过parent = (i-1)/2;计算parent节点位置
因此我们可以计算出最后一个非叶子节点的位置
比如：数组array最大下标是array.size-1，则最后一个非叶子结点的位置是
parent = （array.size-1-1）/2即 (array.size-2)/2
如果已知父节点的位置，通过下面的方式，计算出左右节点的位置
leftPos = 2*parentPos+1;
rightPos = 2*parentPos+2;
2.1 构建大顶堆
大顶堆满足下面两个条件
- 符合完全二叉树
- 所有的父节点的值大于子节点的值
首先来构建一个大顶堆，为了更好的理解，我们画图来一步一步的拆解流程
下面是构建最大堆的代码实现。
void heapify(int* a,int length,int parentPos)
{
if(parentPos >= length)
{
return;
}
//左子节点的下标
int cl = 2*parentPos +1;
//右子节点的下标
int cr = 2*parentPos+2;
//比较 parentPos、cl、cr下标，获取对应的值中最大的值
//首先先假设parentPos下标的值为最大值
int max = parentPos;
//然后和右孩子节点下标对应值进行对比，用max记录最大值的下标
if(cr <length && a[cr]>a[max])
{
max = cr;
}
//再和左孩子节点下标对应值进行对比，用max记录最大值的下标
if(cl <length && a[cl]>a[max])
{
max = cl;
}
//判断是否需要发生位置交换，即max是否有发生变化
if(max !=parentPos)
{
//交换max下标的值和parentPos下标的值
swap(a,max,parentPos);
//然后再用交换的那个点作为parentPos，进行递归调用
//这里为什么会用递归？
//是因为被交换的值可以比它额子节点的值还小，这不符合堆的条件，因此需要依次进行堆化
heapify(a,length,max);
}
}
/**
* @brief 构建 大顶堆
* 满足下面两个条件
* 1. 符合完全二叉树
* 2. 所有的父节点的值大于子节点的值
*
* @param a
* @param length
*/
void buildHeap(int *a,int length)
{
//最后一个节点的下标
int lastNode = length -1;
//最后一个非叶子节点的坐标
int parent = (lastNode -1)/2;
//从最后一个非叶子节点，依次对所有的非叶子节点做heapity堆化处理
for(int i = parent;i>=0;i--)
{
heapify(a,length,i);
}
}
2.2 堆排序
有了大顶堆，我们就可以做第二步的 的堆排序，实现对数组的从小到大的排序
步骤如下：
- 先把根节点和最后一个节点进行交换，这时候最后一个节点的值是最大值。
- 把节点的legth减去1即，去掉最后一个已经确认的最大值
- 从根节点再进行heapify堆化，使得最大值跑到跟节点
我们还是先通过画图来一步一步的拆解流程
最终完整代码实现如下
#include <iostream>
#include<array>
#include<algorithm>
using namespace std;
void printSortArray(int myarray[],int size){
for(int k=0; k<size; k++)
{
cout<<myarray[k]<<" ";
}
cout<<endl;
}
void swap(int *a,int i,int j)
{
int tmp = a[i];
a[i] = a[j];
a[j]=tmp;
}
/**
* @brief 从上到下 逐渐堆化
*
* @param a :堆的数据
* @param length ：堆的长度
* @param parentPos ：堆化的起点位置
*/
void heapify(int* a,int length,int parentPos)
{
if(parentPos >= length)
{
return;
}
//左子节点的下标
int cl = 2*parentPos +1;
//右子节点的下标
int cr = 2*parentPos+2;
//比较 parentPos、cl、cr下标，获取对应的值中最大的值
//首先先假设parentPos下标的值为最大值
int max = parentPos;
//然后和右孩子节点下标对应值进行对比，用max记录最大值的下标
if(cr <length && a[cr]>a[max])
{
max = cr;
}
//再和左孩子节点下标对应值进行对比，用max记录最大值的下标
if(cl <length && a[cl]>a[max])
{
max = cl;
}
//判断是否需要发生位置交换，即max是否有发生变化
if(max !=parentPos)
{
//交换max下标的值和parentPos下标的值
swap(a,max,parentPos);
//然后再用交换的那个点作为parentPos，进行递归调用
//这里为什么会用递归？
//是因为被交换的值可以比它额子节点的值还小，这不符合堆的条件，因此需要依次进行堆化
heapify(a,length,max);
}
}
/**
* @brief 构建 大顶堆
* 满足下面两个条件
* 1. 符合完全二叉树
* 2. 所有的父节点的值大于子节点的值
*
* @param a
* @param length
*/
void buildHeap(int *a,int length)
{
//最后一个节点的下标
int lastNode = length -1;
//最后一个非叶子节点的坐标
int parent = (lastNode -1)/2;
//从最后一个非叶子节点，依次对所有的非叶子节点做heapity堆化处理
for(int i = parent;i>=0;i--)
{
heapify(a,length,i);
}
}
/**
* @brief 进行堆排序
* 有了大顶堆，如何进行堆排序？
* 步骤如下：
* 1. 先把根节点和最后一个节点进行交换，这时候最后一个节点的值是最大值。
* 2. 把节点的legth减去1即，去掉最后一个已经确认的最大值
* 3. 从根节点再进行heapify堆化，使得最大值跑到跟节点
*
* 重复 1、2、3 直到只剩下一个节点
*
*
* @param a
* @param length
*/
void heapSort(int *a,int length)
{
for(int i=length - 1;i>=0;i--)
{
//交换堆的跟节点和最后一个节点
swap(a,0,i);
//交换后在调整为大顶堆，注意此时的长度已经-1，即去掉最后一位已经确认的最大值。
heapify(a,i,0);
}
}
int main(void) {
//用一位数组，表示一个完全二叉树，可以从任意节点拿到它的父节点 和它的左右子节点
int myarray[] ={6,7,1,2,10,5,8,3,4};
int size = sizeof(myarray)/sizeof(myarray[0]) ;
cout<<"size="<<size<<endl;
//首先构建大顶堆
buildHeap(myarray,size);
//然后进行堆排序
heapSort(myarray,size);
printSortArray(myarray,size);
return 0;
}
--》输出结果是：
@"size=9\r\n"
@"1 2 3 4 5 6 7 8 10 \r\n"
堆排序就到这里，下一篇我们继续学习实践选择排序和插入排序，一起学习成长。
三、资料
《漫画算法》
《算法》
[堆排序(heapsort)] ：https://www.bilibili.com/video/BV1Eb41147dK?from=search&seid=12776269936897315206
四、收获
- 了解基本数据结构（ 数组、链表、二叉树、二叉堆）的特点
- 理解并实践构建最大堆
- 理解堆排序的流程并代码实现
感谢你的阅读
下一篇我们继续学习实践排序算法：选择排序和插入排序，欢迎关注公众号“音视频开发之旅”，一起学习成长。
欢迎交流
网友评论