补充概念：若设二叉树的深度为k，除第k层外，其他各层（1～（k-1）层）的节点数都达到最大值，且第k层所有的节点都连续集中在最左边，这样的树就是完全二叉树。如下图：
堆排序参见链接博客
https://www.jianshu.com/p/0d383d294a80
堆排序过程：
创建一个堆 H[0……n-1]；
把堆首（最大值）和堆尾互换；输出堆尾的最大值
把堆的尺寸缩小 1，，剩下的值继续heapify
重复步骤 2，直到堆的尺寸为 1。
对于索引节点为i来说：
父节点：parent = (i-1)/2;
子节点：
c1 = 2i+1;
c2 = 2i+2;
#include<iostream> #include<vector> #include<algorithm> #include<cmath> using namespace std; //堆排序 //对结点堆化 void heapify(vector<int> &arr,int n,int i) { if (i >= n) { return; } int c1 = 2 * i + 1; int c2 = 2 * i + 2; int max = i; if (c1 < n && arr[c1]>arr[max]) { max = c1; } if (c2 < n && arr[c2]>arr[max]) { max = c2; } if (max != i) { swap(arr[max], arr[i]); heapify(arr, n, max); } } //从最后一个结点的父节点开始堆化 void build_heap(vector<int>&arr, int n) { int last_node = n - 1; int parent = (last_node - 1) / 2; //从最后一个结点的父节点做一下 heapfy for (int i = parent; i >= 0; i--) { heapify(arr, n, i); } } void heap_sort(vector<int>& arr, int n) { build_heap(arr, n); for (int i = n - 1; i >= 0; i--) { swap(arr[i],arr[0]);//默认交换第0个结点（最大结点）和 最后一个结点 //对剩下的树进行heapfy heapify(arr, i, 0); } } int main(){ vector<int> arr = { 3,6,5,9,44,56,56,4,6 }; int n = arr.size(); heap_sort(arr, n); for (int i = 0; i < arr.size(); i++) { cout << arr[i] << endl; } system("pause"); return 0; }
时间复杂度：
它是建立在初始构建堆和在重建堆时的反复筛选上，在构建堆的过程中，因为我们是完全二叉树从最下层最右边的非终端结点开始构建，将它与其孩子进行比较和有必要的互换，对于每个非终端结点来说，其实最多的是进行两次比较和呼唤操作，因此整个构建堆的时间复杂度是O（n）;
正式排序的时候，第i次取堆顶记录重建堆需要用O（logi）的时间（完全二叉树的某个结点到根节点的距离为|log2i|+1）,并且需要取n-1次堆顶记录，因此，重建堆的时间复杂度为O（nlogn）
所以总体来说，堆排序的时间复杂度是O（nlogn）。由于堆排序对原始记录的排序并不敏感，因此他无论是最好、最坏、和平均时间复杂度均为O（nlogn）这在性能上远远超过冒泡、简单选择、直接插入的O（n2）的时间复杂度了。
空间复杂度：只有一个用来交换的暂存单元，也非常不错，不过由于记录的比较和交换是跳跃式的进行，因此堆排序也是一种不稳定的排序方法。
另外，由于初始构建堆所需的比较次数较多，因此，并不适合待排序列个数较少的情况。
