用set实现大顶堆

朱雀 2022-08-09 00:57 176阅读 0赞

红黑树通过把节点分为红黑两个颜色并根据一些规则确保树在一定程度上是平衡的，从而保证红黑树中查找、删除和插入操作都只需要O（logk

）时间。而在set和multiset都是基于红黑树实现的。

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

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() 返回一个用于比较元素间的值的函数<div>
 </div>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]);
 			}
 		}
 	}
 }

multiset<int, greater<int>> intset;

可以简单实现大顶堆，如果采用less<int>可以实现小顶堆。

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]);  
             }  
         }  
     }  
 }