void heap_build(vector<int>& nums, int root,int length)
// 某个节点为k,那么他的父节点下标为(k-1)/2,左右子节点下标为2k+1,2k+2
{
int l_child = root * 2 + 1;
if (l_child < length)
{
int flag = l_child;
int r_child = l_child + 1;
if (r_child < length and nums[r_child] > nums[l_child])// 找到最大值
{
flag = r_child;
}
if (nums[root] < nums[flag])//把最大值放到root上
{
int tmp = nums[root];
nums[root] = nums[flag];
nums[flag] = tmp;
heap_build(nums, flag, length);// 看看原来root上的值是否继续下沉
}
}
}
void heap_sort(vector<int> & nums, int len)
// 升序用大顶堆,降序用小顶堆
// 整体主要由构建初始堆+交换堆顶元素和末尾元素并重建堆两部分组成
{
for (int i = len / 2; i >= 0; i--)
{
heap_build(nums,i,len);//从非叶节点开始调整堆
}
for (int j = len - 1; j > 0; j--)// 将最大值往后放,
{
int tmp = nums[0];
nums[0] = nums[j];
nums[j] = tmp;
heap_build(nums,0,j);
}
}
for (int j = len - 1; j > 0; j--)// 将最大值往后放,
{
int tmp = nums[0];
nums[0] = nums[j];
nums[j] = tmp;
heap_build(nums,0,j);
}
问题出现在这里,每一次将最大值往后放了,一个小值放到堆顶,那他跟原来最大值的两个子节点比较很大概率还是小的,他要下沉下去也会浪费更多的步骤。虽然最坏时间复杂度是O(NlogN),但是复杂度的常数项会更大一些。