99999久久久久久亚洲,欧美人与禽猛交狂配,高清日韩av在线影院,一个人在线高清免费观看,啦啦啦在线视频免费观看www

熱線電話：13121318867

登錄
首頁精彩閱讀KD樹的應(yīng)用（2）K個(gè)最小近鄰的查找：大頂堆優(yōu)先級(jí)隊(duì)列
KD樹的應(yīng)用（2）K個(gè)最小近鄰的查找：大頂堆優(yōu)先級(jí)隊(duì)列
2014-12-03
收藏

KD樹的應(yīng)用（2）K個(gè)最小近鄰的查找：大頂堆優(yōu)先級(jí)隊(duì)列

K個(gè)最小近鄰的查找：大頂堆優(yōu)先級(jí)隊(duì)列

    上文中一直在講最近鄰問題，也就是說只找最近的那唯一一個(gè)鄰居，但如果現(xiàn)實(shí)中需要我們找到k個(gè)最近的鄰居。該如何做呢？對(duì)的，之前blog內(nèi)曾相近闡述過尋找最小的k個(gè)數(shù)的問題，顯然，尋找k個(gè)最近鄰與尋找最小的k個(gè)數(shù)的問題如出一轍。

    回憶下尋找k個(gè)最小的數(shù)中關(guān)于構(gòu)造大頂堆的解決方案：

    “尋找最小的k個(gè)樹，更好的辦法是維護(hù)k個(gè)元素的最大堆，即用容量為k的最大堆存儲(chǔ)最先遍歷到的k個(gè)數(shù)，并假設(shè)它們即是最小的k個(gè)數(shù)，建堆費(fèi)時(shí)O（k）后，有k1<k2<...<kmax（kmax設(shè)為大頂堆中最大元素）。繼續(xù)遍歷數(shù)列，每次遍歷一個(gè)元素x，與堆頂元素比較，x<kmax，更新堆（用時(shí)logk），否則不更新堆。這樣下來，總費(fèi)時(shí)O（k+（n-k）*logk）=O（n*logk）。此方法得益于在堆中，查找等各項(xiàng)操作時(shí)間復(fù)雜度均為logk。”

    根據(jù)上述方法，咱們來寫大頂堆最小優(yōu)先級(jí)隊(duì)列相關(guān)代碼實(shí)現(xiàn)：

  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. }  
    上述函數(shù)中，restore_minpq_order的實(shí)現(xiàn)如下：
  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. }  

數(shù)據(jù)分析咨詢請(qǐng)掃描二維碼

若不方便掃碼，搜微信號(hào)：CDAshujufenxi

數(shù)據(jù)分析師資訊
更多

OK
客服在線
立即咨詢
客服在線
立即咨詢
') } function initGt() { var handler = function (captchaObj) { captchaObj.appendTo('#captcha'); captchaObj.onReady(function () { $("#wait").hide(); }).onSuccess(function(){ $('.getcheckcode').removeClass('dis'); $('.getcheckcode').trigger('click'); }); window.captchaObj = captchaObj; }; $('#captcha').show(); $.ajax({ url: "/login/gtstart?t=" + (new Date()).getTime(), // 加隨機(jī)數(shù)防止緩存 type: "get", dataType: "json", success: function (data) { $('#text').hide(); $('#wait').show(); // 調(diào)用 initGeetest 進(jìn)行初始化 // 參數(shù)1：配置參數(shù) // 參數(shù)2：回調(diào)，回調(diào)的第一個(gè)參數(shù)驗(yàn)證碼對(duì)象，之后可以使用它調(diào)用相應(yīng)的接口 initGeetest({ // 以下 4 個(gè)配置參數(shù)為必須，不能缺少 gt: data.gt, challenge: data.challenge, offline: !data.success, // 表示用戶后臺(tái)檢測(cè)極驗(yàn)服務(wù)器是否宕機(jī) new_captcha: data.new_captcha, // 用于宕機(jī)時(shí)表示是新驗(yàn)證碼的宕機(jī) product: "float", // 產(chǎn)品形式，包括：float，popup width: "280px", https: true // 更多配置參數(shù)說明請(qǐng)參見：http://docs.geetest.com/install/client/web-front/ }, handler); } }); } function codeCutdown() { if(_wait == 0){ //倒計(jì)時(shí)完成 $(".getcheckcode").removeClass('dis').html("重新獲取"); }else{ $(".getcheckcode").addClass('dis').html("重新獲取("+_wait+"s)"); _wait--; setTimeout(function () { codeCutdown(); },1000); } } function inputValidate(ele,telInput) { var oInput = ele; var inputVal = oInput.val(); var oType = ele.attr('data-type'); var oEtag = $('#etag').val(); var oErr = oInput.closest('.form_box').next('.err_txt'); var empTxt = '請(qǐng)輸入'+oInput.attr('placeholder')+'！'; var errTxt = '請(qǐng)輸入正確的'+oInput.attr('placeholder')+'！'; var pattern; if(inputVal==""){ if(!telInput){ errFun(oErr,empTxt); } return false; }else { switch (oType){ case 'login_mobile': pattern = /^1[3456789]\d{9}$/; if(inputVal.length==11) { $.ajax({ url: '/login/checkmobile', type: "post", dataType: "json", data: { mobile: inputVal, etag: oEtag, page_ur: window.location.href, page_referer: document.referrer }, success: function (data) { } }); } break; case 'login_yzm': pattern = /^\d{6}$/; break; } if(oType=='login_mobile'){ } if(!!validateFun(pattern,inputVal)){ errFun(oErr,'') if(telInput){ $('.getcheckcode').removeClass('dis'); } }else { if(!telInput) { errFun(oErr, errTxt); }else { $('.getcheckcode').addClass('dis'); } return false; } } return true; } function errFun(obj,msg) { obj.html(msg); if(msg==''){ $('.login_submit').removeClass('dis'); }else { $('.login_submit').addClass('dis'); } } function validateFun(pat,val) { return pat.test(val); }