KD树的应用（2）K个最小近邻的查找：大顶堆优先级队列-CDA数据分析师官网

热线电话：13121318867

KD树的应用（2）K个最小近邻的查找：大顶堆优先级队列

2014-12-03

KD树的应用（2）K个最小近邻的查找：大顶堆优先级队列

K个最小近邻的查找：大顶堆优先级队列

上文中一直在讲最近邻问题，也就是说只找最近的那唯一一个邻居，但如果现实中需要我们找到k个最近的邻居。该如何做呢？对的，之前blog内曾相近阐述过寻找最小的k个数的问题，显然，寻找k个最近邻与寻找最小的k个数的问题如出一辙。

回忆下寻找k个最小的数中关于构造大顶堆的解决方案：

“寻找最小的k个树，更好的办法是维护k个元素的最大堆，即用容量为k的最大堆存储最先遍历到的k个数，并假设它们即是最小的k个数，建堆费时O（k）后，有k1<k2<...<kmax（kmax设为大顶堆中最大元素）。继续遍历数列，每次遍历一个元素x，与堆顶元素比较，x<kmax，更新堆（用时logk），否则不更新堆。这样下来，总费时O（k+（n-k）*logk）=O（n*logk）。此方法得益于在堆中，查找等各项操作时间复杂度均为logk。”

根据上述方法，咱们来写大顶堆最小优先级队列相关代码实现：

		
				void* minpq_extract_min( struct min_pq* min_pq )  
			
				{  
			
				    void* data;  
			
				    if( min_pq->n < 1 )  
			
				    {  
			
				        fprintf( stderr, "Warning: PQ empty, %s line %d\n", __FILE__, __LINE__ );  
			
				        return NULL;  
			
				    }  
			
				    data = min_pq->pq_array[0].data; //root of tree  
			
				    min_pq->n--;   //0  
			
				    min_pq->pq_array[0] = min_pq->pq_array[min_pq->n];  
			
				    restore_minpq_order( min_pq->pq_array, 0, min_pq->n );  
			
				                                              //0  
			
				    return data;  
			
				}

上述函数中，restore_minpq_order的实现如下：

		
				static void restore_minpq_order( struct pq_node* pq_array, int i, int n )  
			
				{                                                          //0     //0  
			
				    struct pq_node tmp;  
			
				    int l, r, min = i;  
			
				    l = left( i ); //2*i+1,????????????  
			
				    r = right( i );//2*i+2,????????????  
			
				    if( l < n )  
			
				        if( pq_array[l].key < pq_array[i].key )  
			
				            min = l;  
			
				    if( r < n )  
			
				        if( pq_array[r].key < pq_array[min].key )  
			
				            min = r;  
			
				    if( min != i )  
			
				    {  
			
				        tmp = pq_array[min];  
			
				        pq_array[min] = pq_array[i];  
			
				        pq_array[i] = tmp;  
			
				        restore_minpq_order( pq_array, min, n );  
			
				    }  
			
				}