四、（1）堆排序
第一次听堆排序是在107lab听忠哥讲的，但是没讲怎么实现。那时刚看了数据结 构的二叉树，还以为要通过指针建立二叉树的方式来实现，觉得挺难的。
其实堆排序实现没有想象中 的那么难。
“堆”这个词最初是在堆排序中提出来的，但后来就逐渐指”废料收集储存区“，就像程 序设计语言Lisp和Java中所提供的设施那样。我们这里的堆数据结构不是废料收集存储区。
堆排序的 运行时间与归并排序一样为O(n lg n), 但是一种原地（in place）排序。
（二叉）堆数据结 构是一种数组对象，它可以被视为一棵完全二叉树。
对于一个数组arr[ ]={16,14,10,8,7,9,3,2,4,1}的 存储数据结构如下图：
在这个结构中，对于每一个根节点i ，要保证它都比他的子节点大
我们可以用一个数组A 【1...length【A】】来表示这个完全二叉树结构。 其中A【1】为根节点1
首先问题是求父节点、左 儿子、右儿子的坐标，通过观察我们可以用宏或者内联函数实现：
// 根据某节点下标i, 计算父节
点、左儿子、右儿子的下标
inline int Parent(int i) { return i>>1; }
inline int Left(int i) { return i<<1; }
inline int Right(int i) { return (i<<1)|1; } //位运算乘2后,结果是偶数所以最后一位一定是0,
所以|1将会把最后一位变成1，从而实现加1的效果
无论是《C++ primer》还是《Effective C++》 ，都讲过宏的缺陷，用内联函数是个更好的选择。位运算做乘除的速度更快。
至于算法演示过程在 《算法导论》上讲得很详细，不再赘述。
堆排序过程需要以下三个函数：
1、Max-Heapify (A,i) : 保持堆的性质,让A【i】在最大堆中“下降”，使以i节点为根的字数成为最大树
以上是小编为您精心准备的的内容，在的博客、问答、公众号、人物、课程等栏目也有的相关内容，欢迎继续使用右上角搜索按钮进行搜索数组
， 数据结构
， 排序
， 堆
， 堆排序
， 算法导论
， 节点
， 计算机科学导论
， 下标
， 二叉树排序
， 算法导论习题堆排序
， 一个
， 堆排序算法
堆排序实现
算法导论 快速排序、归并排序 算法导论、算法导论 堆排序、堆排序 java 算法导论、算法导论，以便于您获取更多的相关知识。