k最近鄰(kNN)算法是一種分類與回歸的方法，假設我們給定一個searching point已脓，打算在訓練數據集中找到一個與該searching point最近的k個數據點梳星，利用多數表決確定這k個點所屬的類邀泉，將該searching point歸入到這個類里面。
kd樹是k近鄰的一種實現(xiàn)方法：為提高搜索效率
構造kd樹
kd樹是數據的一種存儲結構胚迫，是一顆平衡二叉樹喷户，同時也是對數據所在空間的劃分。就是把整個數據空間劃分為幾個部分访锻，然后在特定的空間內進行操作褪尝。
算法直到需要被劃分的子樹為空是停止。
搜索最近鄰：
輸入：已經構造的kd樹期犬，測試樣本x
輸出：x的最近鄰
a)如果kd樹為空河哑，返回null
b)進行二叉查找，在kd樹中找到包含x的葉節(jié)點龟虎，并生成搜索路徑：從根節(jié)點開始璃谨，遞歸的向下訪問kd樹。首先將節(jié)點壓入表示搜索路徑的棧中鲤妥，如果目標點x當前維的坐標小于切分點的坐標佳吞，進入左子節(jié)點，否則進入右子節(jié)點棉安。直到子節(jié)點為空底扳。
c)回溯查找：
根據得到的搜索路徑棧，棧頂的元素為“當前最近點”贡耽，將該元素出棧衷模，并計算該點與x的距離d；
while 棧不空：
????????? 棧頂元素出棧(父節(jié)點)蒲赂；
?????????以x為圓心阱冶，d為半徑畫圓，
???????? if 這個圓與該元素(父節(jié)點)對應的分割超平面相交：
??????????????????計算該元素(父節(jié)點)和x的距離滥嘴，
???????????????????????????if小于d木蹬，則將該元素(父節(jié)點)更新為“當前最近點”，d也需要更新氏涩；
??????????????????同時對元素(父節(jié)點)的另一半子空間的子樹進行步驟b)届囚，搜索的點加入搜索路徑，即壓棧操作是尖；
搜索k近鄰：
方法：最大堆優(yōu)先隊列尋找k近鄰
1）建立一個大小為k的最大堆
2）在尋找最近鄰的算法中意系，每計算一次距離，將對應的樣本和距離加入最大堆中饺汹，直到最大堆建立完成
3）while 尋找最近鄰算法 是否 結束：
???????????? 繼續(xù)尋找最近鄰算法蛔添，并計算距離
???????????? 如果小于堆頂元素：
???????????? ???????????? 則替換，并維護最大堆
堆中的樣本即為x的k個近鄰。建立堆的時間是O（k）迎瞧，更新堆的時間為logk夸溶，總費時為費時O（k+（n-k）*logk）=O（n*logk）。
