k最近邻(kNN)算法是一种分类与回归的方法，假设我们给定一个searching point，打算在训练数据集中找到一个与该searching point最近的k个数据点，利用多数表决确定这k个点所属的类，将该searching point归入到这个类里面。
kd树是k近邻的一种实现方法：为提高搜索效率
构造kd树
kd树是数据的一种存储结构，是一颗平衡二叉树，同时也是对数据所在空间的划分。就是把整个数据空间划分为几个部分，然后在特定的空间内进行操作。
算法直到需要被划分的子树为空是停止。
搜索最近邻：
输入：已经构造的kd树，测试样本x
输出：x的最近邻
a)如果kd树为空，返回null
b)进行二叉查找，在kd树中找到包含x的叶节点，并生成搜索路径：从根节点开始，递归的向下访问kd树。首先将节点压入表示搜索路径的栈中，如果目标点x当前维的坐标小于切分点的坐标，进入左子节点，否则进入右子节点。直到子节点为空。
c)回溯查找：
根据得到的搜索路径栈，栈顶的元素为“当前最近点”，将该元素出栈，并计算该点与x的距离d；
while 栈不空：
栈顶元素出栈(父节点)；
以x为圆心，d为半径画圆，
if 这个圆与该元素(父节点)对应的分割超平面相交：
计算该元素(父节点)和x的距离，
if小于d，则将该元素(父节点)更新为“当前最近点”，d也需要更新；
同时对元素(父节点)的另一半子空间的子树进行步骤b)，搜索的点加入搜索路径，即压栈操作；
搜索k近邻：
方法：最大堆优先队列寻找k近邻
1）建立一个大小为k的最大堆
2）在寻找最近邻的算法中，每计算一次距离，将对应的样本和距离加入最大堆中，直到最大堆建立完成
3）while 寻找最近邻算法 是否 结束：
继续寻找最近邻算法，并计算距离
如果小于堆顶元素：
则替换，并维护最大堆
堆中的样本即为x的k个近邻。建立堆的时间是O（k），更新堆的时间为logk，总费时为费时O（k+（n-k）*logk）=O（n*logk）。
