上篇：6.1.数据结构-c/c++模拟实现堆上篇（向下，上调整算法，建堆，增删数据）-CSDN博客
本章重点
1.使用堆来完成堆排序
2.使用堆解决TopK问题
目录
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;
}
};