欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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;
}