经典九大排序（2）——堆排序

本博客已弃用，当时存在一些小细节错误后期也不再修改了

欢迎来我的

新博客

堆排序

堆排序是一种相当优秀的排序算法，也是大量数据中Top k问题的最优方法，常用于数据量非常大的排序场景。

堆排序把数组看成一颗完全二叉树，利用完全二叉树的父节点与左右孩子节点的下标关系来进行相关排序操作。

我们先回顾一下数组与完全二叉树如何对应起来，对于数组
$A[0...n-1]$
，我们把A的每个元素看成完全二叉树的一个节点，那么，把
$A[0]$
作为其根节点，剩下的
$A[1...n-1]$
逐层从左至右，从上至下依次排列，对于这棵完全二叉树有这样的关系成立

任意节点
$A[i]$

其左孩子为
$A[2i]$
，其右孩子为
$A[2i+1]$
，其父节点为