热线电话：13121318867

登录
首页精彩阅读KD树的应用（2）K个最小近邻的查找：大顶堆优先级队列
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。”

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

  1. void* minpq_extract_min( struct min_pq* min_pq )  
  2. {  
  3.     void* data;  
  4.   
  5.     if( min_pq->n < 1 )  
  6.     {  
  7.         fprintf( stderr, "Warning: PQ empty, %s line %d\n", __FILE__, __LINE__ );  
  8.         return NULL;  
  9.     }  
  10.     data = min_pq->pq_array[0].data; //root of tree  
  11.     min_pq->n--;   //0  
  12.     min_pq->pq_array[0] = min_pq->pq_array[min_pq->n];  
  13.     restore_minpq_order( min_pq->pq_array, 0, min_pq->n );  
  14.                                               //0  
  15.     return data;  
  16. }  
    上述函数中，restore_minpq_order的实现如下：
  1. static void restore_minpq_order( struct pq_node* pq_array, int i, int n )  
  2. {                                                          //0     //0  
  3.     struct pq_node tmp;  
  4.     int l, r, min = i;  
  5.   
  6.     l = left( i ); //2*i+1,????????????  
  7.     r = right( i );//2*i+2,????????????  
  8.     if( l < n )  
  9.         if( pq_array[l].key < pq_array[i].key )  
  10.             min = l;  
  11.     if( r < n )  
  12.         if( pq_array[r].key < pq_array[min].key )  
  13.             min = r;  
  14.   
  15.     if( min != i )  
  16.     {  
  17.         tmp = pq_array[min];  
  18.         pq_array[min] = pq_array[i];  
  19.         pq_array[i] = tmp;  
  20.         restore_minpq_order( pq_array, min, n );  
  21.     }  
  22. }  


CDA数据分析师考试相关入口一览（建议收藏）：

▷ 想报名CDA认证考试，点击>>>   “CDA报名” 了解CDA考试详情；

▷ 想学习CDA考试教材，点击>>> “CDA教材” 了解CDA考试详情；

▷ 想加入CDA考试题库，点击>>> “CDA题库” 了解CDA考试详情；

▷ 想了解CDA考试含金量，点击>>> “CDA含金量” 了解CDA考试详情；

数据分析咨询请扫描二维码

若不方便扫码，搜微信号：CDAshujufenxi

上一篇随机森林 vs XGBoost vs 决策树：算法选择中的
下一篇图论在大数据分析中的作用！
CDA考试动态
CDA报考指南
热门栏目
最新资讯
更多
Copyright © 2015-present 北京国富如荷网络科技有限公司 All Rights Reserved.
京ICP备11001960号-9   京公网安备 11010802034615号   经营许可证编号：京B2-20210330
客服在线
立即咨询