100w个数中找出最大的前K个数
程序员文章站
2024-03-15 22:00:24
...
找出最大的前K个数,这很容易让我们联想到优先级队列,而对是优先级队列中堆又是效率最高的,所以选择使用堆来解决这个问题。
创建小堆小堆堆顶元素为最小的,只要小于最小的就进入队列
创建大小为K的堆遍历数组,大于最小的就进行替换,通过堆的特性,堆重在进行比较,堆顶依旧最小。
#include<iostream>
#include<math.h>
using namespace std;
void _Adjustdown(int* arr, int size, int parent)
{
int child = parent * 2 + 1;
while (child < size)
{
//比较左右节点中较小的一个
if (child + 1 < size && arr[child] > arr[child + 1])
{
child++;
}
if (arr[parent] > arr[child])
{
swap(arr[parent], arr[child]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
//建小堆
void BuildHeap(int *arr, int size)
{
//从第一个非叶子节点开始下滑调整
for (int i = (size - 2) / 2; i >= 0; --i)
{
_Adjustdown(arr, size, i);
}
}
void GetKTop(int* arr, int size, int k)
{
if (size<k || k <= 0)
{
return;
}
//开辟大小为k的空间,把数组中前k个数建小堆
int *heap = new int[k];
for (int i = 0; i < k; ++i)
{
heap[i] = arr[i];
}
BuildHeap(heap, k);
//把后面的数依次和堆顶比较
for (int i = k; i<size; ++i)
{
//如果后面的数大于堆顶,替换掉堆顶,重新调整为最小堆
if (arr[i]>heap[0])
{
heap[0] = arr[i];
_Adjustdown(heap, k, 0);
}
}
for (int i = 0; i < k; ++i)
{
cout << heap[i] << " ";
}
delete[] heap;
}
int main()
{
int arr[100] = { 0 };
int size = sizeof(arr) / sizeof(arr[0]);
for (int i = 0; i < size; ++i)
{
arr[i] = rand() % 100;
}
GetKTop(arr, size, 5);
return 0;
}
上一篇: 在两个⻓度相等的排序数组中找到上中位数
下一篇: java求三个数中的最大值和最小值