堆的应用
关于堆的概念以及堆的创建、删除、插入可以戳这里~
https://blog.csdn.net/Z_JUAN1/article/details/80954426
一、100亿个数中找出最大的前k个数(海量top k 的问题)
分析:
1.首先我们需要建堆,那么是大堆还是小堆?由于要找的是最大的前k个数,那么我们选择建小堆
2.如何建?我们将前k个数进行建堆,此时堆顶的元素就是最小的,用后面的数逐个和堆顶元素比较,若比小堆的堆顶 元素还小,那么堆保持不变,若比堆顶元素大,那么就替换堆顶元素,再次进行调整,使其满足堆的性质。
3.找最小的数就是正好相反。
代码如下~
//建小堆
void AdjustArrayDown(int array[], int size, int parent)
{
int left, right,min;
while (1) {
left = parent * 2 + 1;
right = parent * 2 + 2;
if (left >= size) {
return;
}
min = left;
if (right < size && array[right] < array[left]) {
min = right;
}
if (array[parent] <= array[min]) {
return;
}
swap(array + parent, array + min);
parent = min;
}
}
//找出最大的数
int *TopK(int array[], int size, int k)
{
int i;
int *rarray = (int *)malloc(sizeof(int)*k);
for (i = 0; i < k; i++)
{
rarray[i] = array[i]; //先将前k个数放到rarry中
}
//建堆rarray
for (i = k - 2 / 2; i >= 0; i--){
AdjustArrayDown(rarray, k, i); //对前k个数进行建小堆
}
for (i = k; i < size; i++)
{
if (array[i] > rarray[0]) //只要比最小堆的堆的顶大,就进行替换
rarray[0] = array[i];
AdjustArrayDown(rarray, k, 0);
}
return rarray;
}
二、堆排序(从小到大)
分析
1.建大堆还是小堆?
建小堆:我们建一次就会得到堆顶是最小的,下一次我们依然得通过建堆的方式得到下一个元素,这么下来,我们需要建size-1次的堆
建大堆:我们建一次的到最大的数,使第一个元素和最后一个元素交换位置,我们就得到了最大的那个元素,使size-1,在进行向下调整,得到下一个元素,此时我们建堆只需要建一次
2.综上考虑,我们选择建大堆
代码~
建大堆的代码可以进文章开头链接里的文章获得哦~
//排序
void heapSort(int array[], int size)
{
int i;
for (i = size / 2 - 1; i >= 0; i--)
{
AdjustArrayDown(array, size, i);
}
for (i = 0; i < size; i++){
swap(&(array[0]), &(array[size - 1-i]));
AdjustArrayDown(array, size - 1 - i, 0);
}
}
以上堆的两个应用特别广泛
尤其第一个,比如我们淘宝的时候可以进行选择价格由低到高或由高到低
上一篇: 使用最小堆解决海量数据数据中求TopK最大的几个数问题
下一篇: 猴子吃桃 练习