在许多排序的算法中，堆排序还是比较经典的算法，而且其思想很值得我们学习以及我们思考。
堆排序是基于二叉数的一种算法，叫做二叉堆，相较于二叉树不同的是，二叉堆的所有父节点都比子节点要大或者要小。
首先需要引入最大堆的定义：
最大堆中的最大元素值出现在根结点（堆顶）
堆中每个父节点的元素值都大于等于其孩子结点
现在来简要叙述一下创建最大堆的步骤：
1.先假设父节点的元素最大，标记其index
2.比较父节点和left节点的大小，如果left节点大于父节点，则更新index值为left节点的index。
3.如果步骤二不成立，则比较父节点与right节点的大小，若right节点大于父节点，则更新index值为right节点的index。
4.如果步骤三成立，这比较left节点和right节点的大小，若right节点大于left节点，则更新index值为right节点的index。
5.如果步骤三，四都不成立，也就是说index没有更新，则返回。
6.步骤三，四有一个成立，则交换父节点和index标记位置的值，然后以index标记的位置为父节点继续进行以上步骤。
ps：整个步骤都在子节点的index值要小于树的大小减一（数组是从0开始计数的）。
下面是c++的代码
void createheap(int arr[] ,int n ,int i) { int largest = i; //父节点的值为最大值 int left = 2*i+1; //left节点的位置 int right = 2*i +2; //right节点的位置 if(left < n && arr[left] > arr[largest]) largest = left; //对应步骤二 if(right < n && arr[right] > arr[largest]) largest = right; //对应步骤三 if(largest != i) //对应步骤六 { swap(arr[i],arr[largest]); creatheap(arr,n,largest); //一旦交换，就不知道以该节点为父节点的值是不是最大的，所有又要继续比较。 } }
创建最大堆之后，接下来是进行排序。排序的思想可比创建最大堆要复杂一点，但我们也要静下心来，慢慢思考。
简单来说的话也就是一句话的事：把最大堆堆顶的最大数取出，将剩余的堆继续调整为最大堆，再次将堆顶的最大数取出，这个过程持续到剩余数只有一个时结束。（来自LeetCode）
这个具体的步骤我也解释不太清楚，不过你去画一下图你就知道其中的道理了，如果你能熟练地画出来的话，那么你就应该掌握它了。
void sortheap(int arr[],int n); { for(int i = n/2-1;i>=0;i--) createheap(arr,n,i); for(int i= n-1;i>=0;i--） { swap(arr[0],arr[i]); //先交换堆顶与i位置的元素。 createheap(arr,n,i); //再次生成最大堆 } }
学习于https://mp.weixin.qq.com/s/wqebx4DoeZ-mqA-4uzyFGQ，上面也还有其他的排序算法，大家可以去学习学习。
今天就先分享到这里啦。
thank for your reading ! ! !
公众号：FPGA之旅
