堆排序算法_______没有完成
堆排序的时间复杂度O(N*logN),额外空间复杂度O(1)，是一个不稳定性的排序
准备
堆的结构可以分为大根堆和小根堆，是一个完全二叉树，而堆排序是根据堆的这种数据结构设计的一种排序，下面先来看看什么是大根堆和小根堆
大根堆&&小根堆
性质：每个结点的值都大于其左孩子和右孩子结点的值，称之为大根堆；每个结点的值都小于其左孩子和右孩子结点的值，称之为小根堆。如下图
我们对上面的图中每个数都进行了标记，上面的结构映射成数组就变成了下面这个样子
还有一个基本概念：查找数组中某个数的父结点和左右孩子结点，比如已知索引为i的数，那么
- 父结点索引：(i-1)/2（这里计算机中的除以2，省略掉小数）
- 左孩子索引：2*i+1
- 右孩子索引：2*i+2
所以上面两个数组可以脑补成堆结构，因为他们满足堆的定义性质：
- 大根堆：arr(i)>arr(2i+1) && arr(i)>arr(2i+2)
- 小根堆：arr(i)<arr(2i+1) && arr(i)<arr(2i+2)