STL算法，Heap堆的创建、使用和应用！

STL heap堆的创建和使用

STL中提供了几个关于heap的API，需要基于低一层的容器组件，例如list、vector，Heap是一个类属算法，包含在algorithm头文件之中。

STL对于Heap提供了API，可以让用户手动选择调整成大根堆还是小根堆。

is_heap(first_pointer,last_pointer,cmp_function);
//判断是不是堆

make_heap(first_pointer,last_pointer,cmp_function);//第三个参数默认是less<T>()
// 将一个数组的元素调整成为一个堆的结构。

push_heap(first_pointer,last_pointer,cmp_function);
// 调整堆，假设first 到 last-1是一个堆，则把last的元素加入，重新调整成为一个堆


pop_heap(first_pointer,last_pointer,cmp_function);
// 先将first和last交换位置，然后将fist到last-1的位置重新调整成堆，
// 而末尾元素就是堆的最大值或者最小值

sort_heap(first_pointer,last_pointer,cmp_function);
//对序列进行堆排序，经过排序之后就不再是有效堆了

• 小顶堆：greater<T>() 大顶堆：less<T>()。
• 上述函数中的第三个参数均可以缺省，此时默认是大根堆！

参考链接：https://blog.csdn.net/zsc2014030403015/article/details/45872737

实例

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int main() {

	vector<int> max = { 1,-2,5,4,3,16,7,-8,9 };
	for (auto i : max) {
		cout << i << " ";
	}
	cout << endl;

	cout << "is heap : " << is_heap(max.begin(), max.end(), less<int>()) << endl;//false

	cout << "建立大根堆" << endl;
	make_heap(max.begin(),max.end(),less<int>());//建立一个大顶堆
	for (auto i : max) {
		cout << i << " ";
	}
	cout << endl;			//16 9 7 4 3 5 1 -8 -2

	cout << "is heap : " << is_heap(max.begin(), max.end(), less<int>()) << endl;//true

	/*
	make_heap(max.begin(), max.end(), greater<int>());//建立一个小顶堆
	for (auto i : max) {
		cout << i << " ";
	}
	cout << endl;			//-8 -2 1 4 3 5 7 16 9
	*/
	////////////////////////

	//将一个数据，插入到数组中，重新调整
	max.push_back(20);
	cout << "push : 20" << endl;
	push_heap(max.begin(), max.end());
	for (auto i : max) {
		cout << i << " ";
	}
	cout << endl;				//20 16 7 4 9 5 1 -8 -2 3

	//将最大值移除，然后重新调整
	pop_heap(max.begin(),max.end());
	cout << "end : " << max.back() << endl;
	max.pop_back();
	for (auto i : max) {
		cout << i << " ";
	}
	cout << endl;			//16 9 7 4 3 5 1 -8 -2

	////////////////
	//使用堆排序算法，大根堆排序是将堆顶元素移至末尾！所以是升序排列
	sort_heap(max.begin(),max.end());
	for (auto i : max) {
		cout << i << " ";
	}
	cout << endl;			//-8 - 2 1 3 4 5 7 9 16

	return 0;
}

小总结

• greater是创建小顶堆。而less是创建大顶堆！
• 插入元素，构建堆时，先push_back，然后再push_head。
• 而要取出堆顶元素时，先pop_head，将堆顶元素移至末尾，再pop_back。

实例：使用大顶堆个小顶堆来查找数据流的中位数

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

//得到一个数据流中的中位数

//思路1： 排序，O(logn)

//思路2： 大根堆和小根堆 ， 小根堆元素要大于大根堆，尽量保持元素数量平衡
//小根堆至多比大根堆多一个元素

void InsertData(vector<int> &min, vector<int> &max,int data) {
	if (min.size() > max.size()) {

		//同时还要保证 该元素要有序
		if (data > min[0]) {
			//若大于等于小根堆的最小元素，则小根堆元素先弹出
			pop_heap(min.begin(), min.end(), greater<int>());
			int tmp = min.back();
			min.pop_back();
			
			//将元素插入小根堆
			min.push_back(data);
			push_heap(min.begin(), min.end(), greater<int>());
			data = tmp;
		}

		max.push_back(data);
		push_heap(max.begin(), max.end(),less<int>());
	}
	else {
		//此时 要么元素数量相同，都为0，或者都为一定数目
		if (min.size() == 0) {
			min.push_back(data);
			push_heap(min.begin(), min.end(), greater<int>());
		}

		else {//元素相同，就直接插入大根堆，再将大根堆的最大值插入小根堆
			//先插入大根堆
			max.push_back(data);
			push_heap(max.begin(), max.end(), less<int>());

			//再将大根堆元素插入小根堆
			pop_heap(max.begin(), max.end(), less<int>());
			int tmp = max.back();
			max.pop_back();

			min.push_back(tmp);
			push_heap(min.begin(), min.end(), greater<int>());
		}
	}
}

int GetMedian(vector<int> &min,vector<int> &max) {

	if (min.size() + max.size() == 0) {
		cout << "无元素" << endl;
		return -1;
	}

	if ((min.size() + max.size()) & 1) {
		return min[0];
	}
	else {
		return (min[0] + max[0]) / 2;
	}

	return 0;
}


int main() {

	vector<int> min;//小根堆
	vector<int> max;

	vector<int> nums = { 1,2,3,4,5,6 };
	vector<int> nums1 = { 1,2,3,4,5,6,7 };

	for (auto i : nums1) {
		InsertData(min, max, i);
	}

	cout << GetMedian(min, max) << endl;

	return 0;
}