6.1.数据结构-c/c++堆详解下篇（堆排序，TopK问题）
上篇：6.1.数据结构-c/c++模拟实现堆上篇（向下，上调整算法，建堆，增删数据）-CSDN博客
本章重点
1.使用堆来完成堆排序
2.使用堆解决TopK问题
目录
一.堆排序
1.1 思路
1.2 代码
1.3 简单测试
二.TopK问题
2.1 思路(求最小)：
2.2 C语言代码（手写堆）
2.3 C++代码（使用优先级队列 priority_queue）
一.堆排序
1.1 思路
由于堆的特殊性质，可以使用堆来堆数组进行排序，而且效率较高。
这里以排降序为例。
1.根据数组建堆
2.排序
a.将堆顶数据和最后一个数据交换，n--
b.0~n -1位置还满足向下调整算法。再次调整为堆
c.继续交换
如下图
排升序：建立大根堆
排降序：建立小根堆
1.2 代码
//降序为例
void HeapSort(int* arr, int n)
{//1.将数组建堆,使用向下调整算法建立小根堆for (int i = (n - 1 - 1) / 2; i >= 0; i--){Adjustdown(arr, n, i);}//2.排序//a.将堆顶数据和最后一个数据交换，再让n--，//b.此时0~n-1还是可以使用调整算法调整为堆//c.继续交换int end = n - 1;while (end >= 0){swap(arr[0], arr[end]);Adjustdown(arr, end, 0);end--;}
}1.3 简单测试
测试主函数代码如下
int main()
{DataType arr[] = { 1,5,9,7,5,3,4,6,8,2,4,4,15,19,59,75,73,53,46,82 };cout << "排序前:" << endl;for (int i = 0; i < sizeof(arr) / sizeof(arr[0]); i++){cout << arr[i] << " ";}cout << endl << "排序后:" << endl;HeapSort(arr, sizeof(arr) / sizeof(arr[0]));for (int i = 0; i < sizeof(arr) / sizeof(arr[0]); i++){cout << arr[i] << " ";}return 0;
}测试结果
二.TopK问题
TopK问题是，如何从n个数据中找出前k个最大，或者最小的数据。
Leetcode原题：面试题 17.14. 最小K个数 - 力扣（LeetCode）
2.1 思路(求最小)：
1. 我们建立一个大小为 k 的堆
2. 求最小，建立大根堆。求最大，建立小根堆。
3. 遍历数组，遇到比堆顶数据小的数据 i 时，将数据 i 替换堆顶。然后对堆使用向下调整
举例：
然后遇到4，替换5
遇到6，8不需要替换
遇到2，替换4，并且向下调整，此时3会上浮到堆顶
遇到10，不需要替换。结束。
最后堆的结果为：
即为最小的3个数据
注：题目要求求出最小的k个即可，这k个数据没要顺序要求，若需要，只需调用堆排序即可
2.2 C语言代码（手写堆）
此代码可以直接在题目中运行通过
//向下调整算法，求最小，建立大根堆
void Adjustdown(int*arr,int n,int root)
{int parent=root;int child=parent*2+1;while(child<n){if(child+1<n && arr[child]<arr[child+1] )child++;if(arr[child]>arr[parent]){int t=arr[child];arr[child]=arr[parent];arr[parent]=t;parent=child;child=parent*2+1;}else{break;}}
}int* smallestK(int* arr, int arrSize, int k, int* returnSize)
{*returnSize=k;if(*returnSize==NULL)return NULL;//定义k大小的数组，并拷贝前k个数据，并且调整为堆int *Rarr=(int*)malloc(sizeof(int)*k);for(int i=0;i<k;i++){Rarr[i]=arr[i];}for(int i=(k-1-1)/2;i>=0;i--){Adjustdown(Rarr,k,i);}//TopK法，遍历原数组，遇到比堆顶还要小，删堆顶，插入新元素//这里从k开始，是因为前面已经拷贝了k个数据for(int i=k;i<arrSize;i++){if(arr[i]<Rarr[0]){//1.替换数据Rarr[0]=arr[i];//2.重新调整Adjustdown(Rarr,k,0);}}return Rarr;
}
2.3 C++代码（使用优先级队列 priority_queue）
优先级队列 priority_queue 就是堆，此代码可以直接通过力扣题的测试
//优先级队列
//1.默认的为大根堆
priority_queue<int, vector<int>> pq;//使用greater为小根堆
priority_queue<int, vector<int>, greater<int>>pq;解题代码
class Solution {
public:vector<int> smallestK(vector<int>& arr, int k) {vector<int> retarr(k);if(k==0)return retarr;//使用优先级队列建立大根堆priority_queue<int,vector<int>> pq;//1.拷贝k个数据for(int i=0;i<k;i++){pq.push(arr[i]);}//2.遍历数组，替换比堆顶大的数据for(int i=k;i<arr.size();i++){if(arr[i]<pq.top()){pq.pop();pq.push(arr[i]);}}for(int i=0;i<k;i++){retarr[i]=pq.top();pq.pop();}return retarr;}
};