堆栈总结(三)

一.知识点总结

1.sort函数：用于C++中，对给定区间所有元素进行排序，默认为升序，也可进行降序排序。

sort函数的介绍：sort函数用于C++中，对给定区间所有元素进行排序，默认为升序，
也可进行降序排序。sort函数进行排序的时间复杂度为n*log2n，比冒泡之类的排序算法效率要高

对于vector使用sort排序：
sort(vec.begin(),vec.end()); //可以实现对vector从小到大的排序
sort(vec.begin(),vec.end(),greater<int>()); //可以实现对vector从大到小的排序

对于vector<node>使用sort排序：
struct node {
	int id;
	string name;
}
sort(vec.begin(),vec.end(),cmp);
bool cmp(node a,node b){
	return a.id<b.id //对id进行排序，id小的再前面
}

2.大根堆和小根堆：

最大堆（大根堆）：根结点的键值是所有堆结点键值中最大者。
最小堆（小根堆）：根结点的键值是所有堆结点键值中最小者。

利用c++STL实现：
priority_queue<int> pq1 // 大根堆
priority_queue<int, vector<int>, greater<int>> pq2 // 小根堆

自定义比较函数：
struct cmp {bool operator()(int a,int b) {return a > b;}}; // 自定义小根堆
priority_queue<int, vector<int>, cmp> pq;	

二.小试牛刀

题目1：最小的K个数

最小的K个数很显然只需要排序后对k个数进行记录，然后返回。

题目2：寻找第K大

第K大的数很显然只需要在排序后返回第K个数。

题目3：数据流中的中位数

是栈的灵活应用，我们可以利用两个堆栈，分别去维护左边的最大值和最小值，进而求出中位数。