本文主要是介绍经典排序 之 堆排，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
1. 堆排的时间复杂度为O(nlogn)， 空间复杂度为O(1)。
2. 先上原汁原味手写的代码
void heapAdjust(vector<int>& array, int len, int idx) {int left = idx * 2 + 1; //左孩子int right = left + 1; //右孩子if(left < len || right < len) //先判断是否存在左右孩子{int maxidx = idx; //记录最大值的indexint maxvalue = array[idx]; //记录对应的最大值if(left < len && array[left] > maxvalue){maxvalue = array[left];maxidx = left;}if(right < len && array[right] > maxvalue){ maxvalue = array[right];maxidx = right;}if(idx != maxidx) //如果该节点比左右孩子其中一个要小，则交换，并进一步调整交换后的孩子节点{swap(array[idx], array[maxidx]);heapAdjust(array, len, maxidx);}}
}void heapInit(vector<int>& array) {for(int i = array.size()/2 - 1; i >= 0; i--) //从末尾的 非叶子节点 开始调整heapAdjust(array, array.size(), i);
}void heapSort(vector<int>& array) {heapInit(array); //先初始化堆for(int i = array.size() - 1; i >= 0; i--){swap(array[0], array[i]); //将最大值放到树的最后面heapAdjust(array, i, 0); //数组长度一直随着i在变小，然后从根开始调整}
}堆排的思想基于构造一个完全二叉树，以最小堆为例子，步骤为：先初始化堆，然后逐次把根(最大值)放到树的末尾，并从根处重新调整。
注意点：a. 当树的下标为01234时，对于下标为 i 的节点，左右孩子分别 2*i+1, 2*i+2。
b. 注意树长度和相应坐标的关系。
c. 初始化堆时，其实可以只从非叶子节点开始，对应的坐标为(array.size()/2 - 1)，不要搞错。如果容易记错，可以直接从末尾array.size()-1开始，这样进入adjust里也不会进行调整，不影响结果。
3. 堆排经常用于 top k 这样的问题上面。
这篇关于经典排序 之 堆排的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
