用multiset/priority_Queue来实现最大最小堆

面试题：实现KNN，给定各个点之间的距离，返回某个点的k个neighbor。

思路： 考虑到A家喜欢问海量数据，所以用heap，复杂度O(nlogk)。 当时是自己实现的heap。后来发现可以直接调用STL中的set 或者multiset来实现。
              

Mulitiset: STL中 set 和multiset

set的含义是集合，它是一个有序的容器，里面的元素都是排序好的，支持插入，删除，查找等操作，就 像一个集合一样。所有的操作的都是严格在logn时间之内完成，效率非常高。 set和multiset的区别是：set插入的元素不能相同，但是multiset可以相同。（本例中使用距离作为比较元素，而距离是很有可能）

typedef struct{
	int index;
	double length;
}Info;

typedef struct{
	bool operator()(const Info& info1,  const Info& info2){
		if ((info1.length - info2.length) > 0)
			return true;
		return false;
	}
}Comp;
typedef multiset<Info,Comp> intSet;
void GetLeastNumbers(const vector<Info>& data,int length, int k, intSet& result){
	result.clear();

	for(int index = 0;index <length ;index++){
		if (result.size()<k)
			result.insert(data[index]);
		else{
			if (data[index].length < result.begin()->length){
				result.erase(result.begin());
				result.insert(data[index]);
			}
		}
	}
}

1. 关于运算符重载：http://blog.csdn.net/candy20094369/article/details/6749171

2. multiset常用操作：

insert() 在集合中插入元素
begin() 返回指向第一个元素的迭代器，end() 返回指向最后一个元素的迭代器
clear() 清除所有元素
count() 返回某个值元素的个数 （如果是set，返回值不是1，就是0）
empty() 如果集合为空，返回true
equal_range() 返回集合中与给定值相等的上下限的两个迭代器
erase() 删除集合中的元素
find() 返回一个指向被查找到元素的迭代器
get_allocator() 返回集合的分配器
ower_bound() 返回指向大于（或等于）某值的第一个元素的迭代器
key_comp() 返回一个用于元素间值比较的函数
max_size() 返回集合能容纳的元素的最大限值
rbegin() 返回指向集合中最后一个元素的反向迭代器
rend() 返回指向集合中第一个元素的反向迭代器
size() 集合中元素的数目
swap() 交换两个集合变量
upper_bound() 返回大于某个值元素的迭代器
value_comp() 返回一个用于比较元素间的值的函数

3.  本例子用的是最大推，主要考虑是因为这样可以方便删除较大的值（否则用反向迭代器）

————————————————————————————————————————我是分割线——————————————————————————

priority_queue 调用 STL里面的 make_heap(), pop_heap(), push_heap() 算法实现，也算是堆的另外一种形式。与heap一样，都调用

#include<algorithm>

priority_queue 对于基本类型的使用方法相对简单。
他的模板声明带有三个参数，priority_queue<Type, Container, Functional>
Type 为数据类型， Container 为保存数据的容器，Functional 为元素比较方式。
Container 必须是用数组实现的容器，比如 vector, deque 但不能用 list. STL里面默认用的是 vector. 比较方式默认用 operator< , 所以如果你把后面俩参数缺省的话，优先队列就是大顶堆，队头元素最大。

typedef priority_queue<Info, vector<Info>,Comp> intPriority;

typedef struct{  
    bool operator()(const Info& info1,  const Info& info2){  
        if ((info1.length - info2.length)< 0)  
            return true;  
        return false;  
    }  
}Comp;
void GetLeastNumbers(const vector<Info>& data,int length, int k, intPriority& result){  
    for(int index = 0;index <length ;index++){  
		if (result.size()>0)
			Info temp = result.top();
        if (result.size()<k)  
            result.push(data[index]);  
        else{  
	     if (data[index].length < result.top().length){  
                result.pop();  
                result.push(data[index]);  
            }  
        }  
    }  
}  

————————————————————————分割线——————————————————————————————————

关于stl中heap的实现

http://blog.csdn.net/morewindows/article/details/6967409