数据结构之堆排序

1 堆排序

堆排序（英语：Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点，我们可以理解构建的堆是 完全二叉树 ，它们的下标有如下性质

完全二叉树还有这个性质，比如这个树有n个节点，那么这个树的有左右孩子节点的父节点有n / 2个，如果我们堆顶是从下标0开始的，那么n / 2个数就对于于下标0~ (n / 2 - 1),而且如果当前节点是下标i的话（有左右子节点情况），那么它的左孩子节点的下标是2*i + 1，右孩子节点下标是2 * i + 2, 如果我们堆顶是从下标1开始的，那么n / 2个数就对于于下标0~ (n / 2),而且如果当前节点是下标i的话（有左右子节点情况），那么它的左孩子节点的下标是2*i ，右孩子节点下标是2 * i + 1, 

2 构建大顶堆过程分析

1）我们需要知道这个数组构建堆后有多少节点拥有左或者右孩子节点，因为满足完全二叉树，

文章来源: chenyu.blog.csdn.net，作者：chen.yu，版权归原作者所有，如需转载，请联系作者。

原文链接：chenyu.blog.csdn.net/article/details/102878213