堆排序(Heapsort )是利用堆这种数据结构所设计的一种排序算法。

堆的概念

堆是具有以下性质的完全二叉树∶

  1. 每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆;
  1. 每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。如下图:

我们对堆中的结点按层进行编号，将这种逻辑结构映射到数组中就是下面这个样子

对于某1个节点i,它的父节点(i-1)/2
对于某1个节点i,它的左孩子2i+1
对于某1个节点i,它的右孩子2i+2

堆排序的思路

（1）根据初始数组去构造初始堆。
（2）每次交换第一个和最后一个元素，输出最后一个元素(最大值），然后把剩下元素重新调整为大根堆，再进行交换第一个元素和最后一个元素，再调整大顶堆，重复执行，直到整个数组排序完成。

建堆的过程∶

现在我们有一个无序数组:27,46,12,33,49,27,36,40,42,50,51，我们先把它建成完成二叉树，然后从最后一个非叶子结点开始，从右至左，从下至上进行调整，将它调整成大顶堆。

最后一个非叶子结点的下标:(arr.length-1-1)/2 = arr.length/2-1

堆排序的过程:

将堆顶元素与末尾元素交换，将最大元素”沉”到数组末端，调整堆结构(heapify)，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素，反复操作，直到堆里只剩下1个元素。

例如∶将堆顶元素与末尾元素交换，即51和27交换，51”沉”到数组末端。

对剩余元素调整堆结构得到:

继续将堆顶元素与末尾元素交换，即50和27交换，50”沉”到数组倒数第2的位置。

以此类推，继续调整堆结构，继续交换堆顶和堆尾元素，直到堆里只剩下1个元素，整个堆排序完成。