堆排序是一种不管最佳情况还是最糟情况，时间复杂度都是O(NlogN)的一种排序算法。
这种算法将目标源数组抽象化成一个堆（heap），并且根据增序降序的要求再分别转化为大顶堆和小顶堆。
堆是一种数据结构，可以看成一种近似的完全二叉树，只不过该二叉树必须满足左侧填充。而大顶堆的特性则是父节点必须大于等于孩子节点，也就是说大顶堆的根节点必须是当前数据中数值最大的元素。
上图a就是一个大顶堆。
堆还有一个特性就是索引值与堆节点位置的互相对应。例如图a，堆中的最后一个父节点肯定是堆中节点数量 / 2（数组中的索引值就是末尾元素索引值 / 2）。
所以，为了进行排序，我们初始化大顶堆后每次循环需要做的步骤有以下几个：
1.将首元素与末尾元素（当前容量的末尾而不是数组的末尾）交换
2.将堆的容量减1
3.维护交换后的根节点，保证交换后的堆仍是大顶堆
4.回到1，终止条件为容量为1
这样每次都会把数组中的最大元素提取出来放到末尾，做到一个递增的效果。
首先是维护大顶堆
1 /// <summary> 2 /// 自顶向下维护堆为大顶堆 3 /// </summary> 4 /// <param name="nums">数据</param> 5 /// <param name="n">要从第n个数据开始自顶向下维护</param> 6 /// <param name="size">目前大顶堆的容量</param> 7 void keepMaxHeap(vector<int>& nums, int n, int size) { 8 int left = 2 * n + 1, right = 2 * n + 2; //当前节点的左右孩子 9 int maxIndex = 0; //找出左右孩子谁的数值更大 10 if (left <= size && nums[n] <= nums[left]) { 11 maxIndex = left; 12 }else { 13 maxIndex = n; 14 } 15 if (right <= size && nums[maxIndex] <= nums[right]) { 16 maxIndex = right; 17 } 18 19 //如果最大节点不是本身，则自身数值和最大数值孩子交换数值 20 if (maxIndex != n) { 21 int temp = nums[n]; 22 nums[n] = nums[maxIndex]; 23 nums[maxIndex] = temp; 24 keepMaxHeap(nums, maxIndex, size); //顺着刚才交换的节点继续维护 25 } 26 }
初始化大顶堆
1 /// <summary> 2 /// 构造大顶堆（初始化） 3 /// </summary> 4 /// <param name="nums">数据</param> 5 void buildMaxHeap(vector<int>& nums) { 6 //数组的中间元素为最后一个有叶子节点的父节点 7 for (int i = (nums.size() - 1) / 2; i >= 0; i--) { 8 keepMaxHeap(nums, i, nums.size() - 1); 9 } 10 }
最终排序函数
1 /// <summary> 2 /// 堆排序 3 /// </summary> 4 /// <param name="nums">数据</param> 5 void heapSort(vector<int>& nums) { 6 buildMaxHeap(nums); //先初始化大顶堆 7 int count = 0; 8 //当完成第二个元素的交换后，就没元素可以交换了 9 for (int i = nums.size() - 1; i >= 1; i--) { 10 int temp = nums[i]; //交换首尾元素 11 nums[i] = nums[0]; 12 nums[0] = temp; 13 count++; 14 15 //每将大顶堆的首元素（最大元素）放到后面后，就将容量减1 16 //交换后维护根节点，保证更新后的堆仍为大顶堆 17 keepMaxHeap(nums, 0, nums.size() - 1 - count); 18 } 19 }