【C語言】數組的top-k 的兩種實作方式

轉載于：https://zhuanlan.zhihu.com/p/37350934

這兩種方式都是使用堆的思路來做的，是以時間複雜度相比于其他的實作快一點。

1、第一種代碼 ，預設是浮點型的topk，如果需要切換成整形數組topk，應注意把代碼所有地方的float 類型改成 float

由于c語言對類型轉換非常敏感，整形轉浮點型可能會導緻精度損失，比如float類型的 0.3333 直接指派int類型，就會直接置為0。務必注意！

/* 
尋找n個不同資料中第k大的元素 
接口：int top_k(int *a,int n,int k);  
輸入：一個由n個不同元素組成的數組a，a的長度n以及k的值  
輸出：數組a中第k大的元素  
*/  
  
#include<stdio.h>  
#define max_size 10001  
  
float min_heap[max_size]={0.0};    //假定數組中的數都是正數     
int heap_count=0;  
  
void reheap(int k)         //更新根節點的數值後，調整使其符合最小堆  
{  
    int root=0;  
    int child=root*2+1;  
    while(child<k)  
    {  
        if((child+1)<k&&min_heap[child+1]<min_heap[child])  
            child++;  
        if(min_heap[root]<min_heap[child])  
            return;  
        float temp=min_heap[root];  
        min_heap[root]=min_heap[child];  
        min_heap[child]=temp;  
        root=child;  
        child=root*2+1;  
    }  
}  
  
float top_k(float *a,int n,int k)  
{  
    int i;  
    for(int i=0;i<n;i++)  
        if(a[i]>min_heap[0])  
        {  
            min_heap[0]=a[i];  
            reheap(k);  
        }  
    return min_heap[0];  
}  
  
int main(void)  
{  
     
    float array[10]={1.2,4.5,2.4,5.6,7.6,7.8,5.8,7.8,9.1,3.8}; 
    float x=top_k(array,9,5);
    printf("%.1f\n",x);  
      
    return 0;  
} 
           

第二種實作方式：

提供第k大的數和第k小的數，兩種方案；預設求解的是第k大的數

#include<stdio.h>
//topk   第k大的數
void maxHeapify(float* a, int i, int heapSize)
{
    int l = i * 2 + 1, r = i * 2 + 2, largest = i;

    if (l < heapSize && a[l] > a[largest])
    {
        largest = l;
    }

    if (r < heapSize && a[r] > a[largest])
    {
        largest = r;
    }

    if (largest != i)
    {
        float t = a[i];
        a[i] = a[largest], a[largest] = t;
        maxHeapify(a, largest, heapSize);
    }
}

//topk   第k小的數
void minHeapify(float* a, int i, int heapSize)
{
    int l = i * 2 + 1, r = i * 2 + 2, largest = i;

    if (l < heapSize && a[l] < a[largest])
    {
        largest = l;
    }

    if (r < heapSize && a[r] < a[largest])
    {
        largest = r;
    }

    if (largest != i)
    {
        float t = a[i];
        a[i] = a[largest], a[largest] = t;
        minHeapify(a, largest, heapSize);
    }
}

void buildMinHeap(float* a, int heapSize)
{
    for (int i = heapSize / 2; i >= 0; --i)
    {
        maxHeapify(a, i, heapSize);
    }
}

float findKthLargest(float* nums, int numsSize, int k)
{
    int heapSize = numsSize;
    buildMinHeap(nums, heapSize);

    for (int i = numsSize - 1; i >= numsSize - k + 1; --i)
    {
        float t = nums[0];
        nums[0] = nums[i], nums[i] = t;
        --heapSize;
        maxHeapify(nums, 0, heapSize);
    }


    return nums[0];
}

int main(void)
{
    float array[10]={0.14,0.12,0.13,0.11,0.18,0.11,0.17,0.19,0.16,0.15};
    
    printf("%f\n",findKthLargest(array,10,5));
  
    return 0;
}