堆排序
堆是一种叫做完全二叉树的数据结构，可以分为大根堆和小根堆。 大根堆：每个节点的值都大于或者等于它的左右孩子的值 小根堆：每个节点的值都小于或者等于它的左右孩子的值
完全二叉树在数组中的存储
当二叉树按层序遍历的顺序保存在数组中时，如果根节点存放在array[0]，则节点i的左孩子节点为array[i*2 1]，右孩子节点为array[i*2 2]；如果根节点存放在array[1],则其左孩子为array[i*2],其右孩子为array[i*2 1]。
建堆过程(大根堆为例)
从最后一个父节点array[n/2]开始，往前遍历，判断父节点和两个孩子节点大小，如果有孩子比父节点还大的，交换，这个交换会导致子树不符合大根堆的特点，因此要再往下再调整子树，直到调整完所有的，就构建好了大根堆 注：其中n是元素的个数。 ###代码 堆排序实现找第k大数，采用大根堆的方法
代码语言：javascript复制class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
//建堆
bigRootHeaps(nums,nums.size());
//交换k-1个元素去堆底，下一个堆根即为第k大个元素
for(int i=0;i<k-1;i )
{
//交换
int temp=nums[0];
nums[0]=nums[nums.size()-1-i];
nums[nums.size()-1-i]=temp;
//调整,只需要调整交换的那个子树即可
change(nums,0,nums.size()-i-1);
}
return nums[0];
}
void bigRootHeaps(vector<int>&nums,int len)
{
for(int i=len/2;i>=0;i--)
{
change(nums,i,len);
}
}
void change(vector<int>&nums,int i,int len)
{
int left_child=i*2 1;
int right_child=i*2 2;
int largest=i;
if(left_child<len&&nums[left_child]>nums[i])
largest=left_child;
if(right_child<len&&nums[right_child]>nums[largest])
largest=right_child;
if(largest!=i){
int temp=nums[i];
nums[i]=nums[largest];
nums[largest]=temp;
change(nums,largest,len);
}
}
};执行用时：144 ms, 在所有 C 提交中击败了14.16%的用户
内存消耗：44.4 MB, 在所有 C 提交中击败了65.45%的用户
通过测试用例：39 / 39效果跟快排旗鼓相当：http://8.130.83.240/article/2023/3/19/9.html
找最大k个元素的堆排序优化
可以采用小根堆而不是大根堆的方式来实现，小根堆只维护k个元素，减少了堆调整的次数 小根堆存放k个元素，根节点存储这k个元素中的最小值 在解决这个问题时:
- 首先把前k个元素读入堆中，然后维护成一个小根堆；
- 由于要求最大的前k个值，之后都进来的元素，如果比小根堆的根节点还小，则直接丢弃，因为它不可能是top K元素了；
- 如果比根节点的元素大，则替换根节点，并调整小根堆，使其符合小根堆的特性；
- 遍历完所有元素后，小根堆的根节点就是我们要找的第k大个元素；
小根堆解决方法代码实现
代码语言：javascript复制class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
//存放前k个元素的数组
vector<int>array;
//初始化数组，先存k个数进去
for(int i=0;i<k;i )
{
array.push_back(nums[i]);
}
//建堆
smallRootHeaps(array,k);
for(int i=k;i<nums.size();i )
{
//如果之后的元素甚至比小根堆根节点还小，直接丢掉
if(nums[i]<=array[0])
continue;
else{
//否则将这个元素放入小根堆根节点
array[0]=nums[i];
//调整使其符合小根堆特性
change(array,0,k);
}
}
return array[0];
}
void smallRootHeaps(vector<int>&nums,int len)
{
for(int i=len/2;i>=0;i--)
{
change(nums,i,len);
}
}
void change(vector<int>&nums,int i,int len)
{
int left_child=i*2 1;
int right_child=i*2 2;
int min=i;
if(left_child<len&&nums[left_child]<nums[min])
min=left_child;
if(right_child<len&&nums[right_child]<nums[min])
min=right_child;
if(min!=i){
int temp=nums[i];
nums[i]=nums[min];
nums[min]=temp;
change(nums,min,len);
}
}
};执行用时：96 ms, 在所有 C 提交中击败了50.23%的用户
内存消耗：46.1 MB, 在所有 C 提交中击败了19.67%的用户
通过测试用例：39 / 39对比使用大根堆，效率提升了一大截，因为除去调整小根堆和建堆的时间，效率接近O(n),但是由于使用了辅助数组，内存占用多了一点，也可以不用辅助数组而直接在nums的前k个位置建小根堆，比较简单，就不实现了。
