优先级队列解决top-K问题(C语言实现)

骑猪看日落 2023-03-01 05:37 13阅读 0赞

对于数组\{10, 4, 3, 6, 5, 8, 9, 3\}，希望求第k (k = 3) 大的数据。  
如果用传统的思路解决这个问题：先用快速排序对整个数组排序。然后取第K个元素，这种方式的时间复杂度为O(N \* logN)。如果n非常大，对整个数组排序需要使用外部排序 (内存中放不下，需要硬盘辅助排序)。如果使用大小为k的小顶堆，就有可能在内存中完成这个任务。也就是说，这个方法不仅可以降低时间复杂度，还可以降低内存的消耗。

这里用小顶堆的方式进行计算：取前面3个元素，建立一个小顶堆，然后遍历其它元素，如果某个元素比堆顶元素还要小，则丢弃该元素；如果该元素比堆顶元素大，则用它代替堆顶元素，并维护这个堆。最后，这个堆中的元素就是这个数组中最大的三个元素，这个堆顶元素就是第3大的数据。如果希望得到的是最大的3个数据，输出这个堆中的三个元素即可。

这个堆一共k个元素，所以维护一次堆的时间复杂度为O(logK)。遍历(N - k)个元素，并维护堆的时间复杂度为O((N - k) \* logK)。  
最好的情况，K = 1，不需要维护堆，所以时间复杂度为O(N)；最差的情况，K = N，也就是用小顶堆求最小的那个元素，这时几乎所有时间都花费在建立一个大小为N的小顶堆，时间复杂度为O(N \* logN)。与进行堆排序后取第K个元素的时间复杂度一样。但是如果是这种情况，用大顶堆计算，时间复杂度又是O(N)；平均情况，如果K == N / 2，则时间复杂度为O(N \* logN)；一般情况下，k的值远小于N，所以时间复杂度为O(N \* logK)。

这种求top-K的方法属于部分排序。如果k < logN，可以考虑用选择排序，如果k >= logN，可以使用本方法。

完整的代码如下：

#include <stdio.h>
    #include <stdlib.h>
    
    int arr [] = {
        10, 4, 3, 6, 5, 8, 9, 3};
    int sizeOfHeap = 3; //第k (k = 3) 大的数据，维护一个大小为3的小顶堆
    int size = 0; //数组的大小 
    
    void swap(int i, int j) //交换数组arr中编号为i和j的两个元素 
    {
        
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
    
    //寻找3个元素中的最小值
    int getMin(int father, int leftSon, int rightSon)  
    {
        
    	int minIndex = father; //较小元素的index
    	int min = arr[father]; //较小元素的值 
    	
    	if(leftSon < sizeOfHeap && arr[leftSon] < min)
    	{
        
    		min = arr[leftSon];
    		minIndex = leftSon;
    	}
    	if(rightSon < sizeOfHeap && arr[rightSon] < min)
    	{
        
    		//min = arr[rightSon]; //这一行代码是多余的 
    		minIndex = rightSon;
    	}
    	return minIndex; //返回最小值的元素的编号 
    }
    
    //向下调整函数
    //传入一个需要向下调整的结点编号i。
    //这里一直传入0，即从堆的顶点开始向下调整
    void shiftDown(int i)
    {
        
        int minIndex = 0; //较大元素的index
        while(true)
        {
        
        	//左儿子的编号是i * 2 + 1，右儿子的编号是i * 2 + 2 
        	minIndex = getMin(i, i * 2 + 1, i * 2 + 2); 
            
    		if(minIndex != i) //父节点不是最小结点时 
    		{
        
    			swap(minIndex, i); //交换，使父节点成为最小结点 
    			i = minIndex; //更新i结点，继续向下调整 
    		}
            else //父节点是最小结点时 
            {
        
                break; //退出循环 
            }
        }
    }
    
    //建立小顶堆的函数
    void createMinHeap()
    {
        
        //从最后一个非叶结点到第0个结点一次进行向上调整
        //维护一个3个元素的堆
        for (int i = sizeOfHeap / 2; i >= 0; i--)
        {
        
            shiftDown(i);
        }
    }
            
    int main()
    {
        
    	int size = sizeof(arr) / sizeof(int); //计算数组大小 
        createMinHeap(); //建堆
    
        //遍历剩余元素
        for (int i = sizeOfHeap; i < size; i++)
        {
        
            printf("开始： %d, %d, %d\r\n", arr[0], arr[1], arr[2]);
            
    		//如果其它元素比堆顶元素还要小，则丢弃该元素
            if (arr[i] <= arr[0])
            {
        
                printf("新元素：%d，丢弃。剩余： %d, %d, %d", arr[i], arr[0], arr[1], arr[2]);
            }
            else
            {
        
                //如果比堆顶元素大，则用它代替堆顶元素，并维护这个堆。
                arr[0] = arr[i];
    
                //这个堆只有三个元素，每次都要判断0元素是否要向下调整
                shiftDown(0);
                printf("新元素：%d，替换首元素，调整小顶堆后：%d, %d, %d", arr[i], arr[0], arr[1], arr[2]);
            }
            printf("\r\n\r\n");
        }
    
        //最后，这个堆顶元素就是第3大的数据。剩余两个元素的值的次序是无所谓的
        printf("第3大的元素是：%d\r\n\r\n", arr[0]);
        printf("数组中最大的三个元素是：%d, %d, %d\r\n\r\n", arr[0], arr[1], arr[2]);
        printf("能保证首元素比另外两个元素小，但不能保证后面两个元素的次序。");
        return 0;
    }

运行结果：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdlaWwwMDc_size_16_color_FFFFFF_t_70]Top-K问题是很常见的，例如用搜索引擎搜索的时候，可能搜出10000个结果，但是网站上只显示最前面的10个结果。如何快速的从这10000个结果中找到前10个结果，这就是典型的top-K问题。  
我们在药物设计时可能设计出上万个结构 (甚至更多)，药物设计者往往只是对得分最高的10个结构感兴趣。我们需要把设计出来的药物与模板药物进行对比和打分，选取得分最高的1000个结构，这也是用top-K方法解决的。在得到这1000个结构之后，还需要进行一次堆排序，将数据输出。这样就可以得到得分从高到低的结构。Top-K问题的终极解决方案是本书的压轴算法：线性查找。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdlaWwwMDc_size_16_color_FFFFFF_t_70]: /images/20230209/3db8e77dbac8473fb190a240094729b7.png