堆排序原理及代码

---

你的点赞评论就是对博主最大的鼓励
当然喜欢的小伙伴可以：点赞+关注+评论+收藏（一键四连）哦~

---

🍊自我介绍

  Hello,大家好，我是小珑也要变强（也是小珑），我是易编程·终身成长社群的一名“创始团队·嘉宾” 和“内容共创官” ,现在我来为大家介绍一下有关物联网-嵌入式方面的内容。

---

🍊堆排序

一、什么是堆？

堆是一种类似完全二叉树的数据结构，可以分为大顶堆，小顶堆（也叫大根堆，小根堆），而堆排序就是基于这种结构而产生的一种程序算法。

二、堆的分类

分类
大顶堆：每个节点的值都大于或者等于其左右孩子的值。
小顶堆：每个节点的值都小于或者等于其左右孩子的值。

堆排序：若是需要进行堆排序的代码，一定需要先把树构建成大顶堆或者小顶堆，然后再进行排序。

🍊堆排序的思路

以下以数组 [4, 6, 8, 5, 9] 为例来梳理堆排序的思路。

一、构建大顶堆

1. 首先明确完全二叉树的性质，对于数组中的元素，节点 i 的左子节点为 2 * i + 1 ，右子节点为 2 * i + 2 。
2. 从最后一个非叶子节点开始调整，数组长度为 5，最后一个非叶子节点索引为 (5/2 - 1)=1 ，对应元素值为 6。

• 以索引为 1 的节点（值为 6）为当前节点，左子节点索引为 3（值为 5），右子节点索引为 4（值为 9），比较三个值，9 最大，所以交换当前节点的值 6 和索引为 4 的节点的值 9。
• 此时数组变为 [4, 9, 8, 5, 6] 。

3. 接着处理索引为 0 的节点（值为 4）。

• 左子节点索引为 1（值为 9），右子节点索引为 2（值为 8），比较三个值，9 最大，所以交换当前节点的值 4 和索引为 1 的节点的值 9。
• 此时数组变为 [9, 4, 8, 5, 6] 。

经过上述步骤，大顶堆构建完成。

二、排序过程

1. 此时堆顶元素 9 为最大值，将堆顶元素 9 与最后一个元素 6 交换。

• 数组变为 [6, 4, 8, 5, 9] 。

2. 由于交换后可能破坏了堆的性质，需要从堆顶开始调整堆，这里调整的堆大小为 4（因为已经确定了一个最大元素在最后位置）。

• 以索引为 0 的节点（值为 6）为当前节点，左子节点索引为 1（值为 4），右子节点索引为 2（值为 8），比较三个值，8 最大，所以交换当前节点的值 6 和索引为 2 的节点的值 8。
• 此时数组变为 [8, 4, 6, 5, 9] 。

3. 重复上述过程，再次将堆顶元素 8 与当前未排序部分的最后一个元素 5 交换。

• 数组变为 [5, 4, 6, 8, 9] 。
• 调整堆，以索引为 0 的节点（值为 5）为当前节点，左子节点索引为 1（值为 4），无子节点，无需交换。

4. 最后将堆顶元素 5 与当前未排序部分的最后一个元素 4 交换。

• 数组变为 [4, 5, 6, 8, 9] 。

此时数组已经完全有序。堆排序完成。

🍊堆排序代码

#include <stdio.h>void swap_data(int *x,int *y)
{*x ^= *y;*y ^= *x;*x ^= *y;return ;
}//自调整构建大顶堆
void heap_adjust(int *arr,int start,int end)
{int father_node = start;int son_node = father_node * 2 + 1;while(son_node <= end){//比较两个子结点，找到较大的字节if(son_node + 1 <= end && arr[son_node] < arr[son_node + 1])	{son_node ++;	}//若是父节点 > 子节点 ,表示调整完毕if(arr[father_node] > arr[son_node]){return ;	}else{ //交换负责父子内容，在继续子节点与孙结点比较swap_data(&arr[father_node],&arr[son_node]);father_node = son_node;son_node = father_node * 2 + 1;}}return ;
}void heap_sort(int arr[],int len)
{int i = 0;//第一次建立大顶堆，找到从右到左,找到第一次非叶子结点//从后往前依次遍历for(i = len / 2 - 1;i >= 0;i--){heap_adjust(arr,i,len - 1);	}//每次将根结点和最后一个结点交换，然后在调整for(i = len - 1;i > 0;i--){swap_data(&arr[0],&arr[i]);	heap_adjust(arr,0,i - 1);}
}void print_array(int a[],int plen)
{int i = 0;for(i = 0;i < plen;i++){printf("%d ",a[i]);	}printf("\n");
}int main()
{int a[] = {15,7,3,20,17,8};	int len = sizeof(a)/sizeof(a[0]);print_array(a,len);heap_sort(a,len);print_array(a,len);return 0;
}