使用STL容器构造堆数据结构

STL_Heap_Struct.md

• 使用STL中的优先级队列进行堆数据结构的建立

priority_queue<Type, Container, Functional>
Type - 数据类型
Container - 保存数据的容器
Functional - 用来指定数据之间的比较规则

STL中的默认的priority_queue是存储类型为vector的大顶堆，使用方式如下
priority_queue<int, vector<int>, less<int>> high_heap;
我们也可以使用默认的缺省的构造函数
priority_queue<int> high_heap;
如果我们想使用小顶堆，可以按照如下的数据结构进行处理
priority_queue<int, vector<int>, greater<int>> low_heap;

• 对于自定义的数据类型，我们可以使用如下方法进行堆结构的创建

struct Node {
	int x, y;
};
bool operator < (const Node& a, const Node& b) {
	if(a.x == b.x) return a.y > b.y;
	return a.x > b.x;
}

priority_queue<Node> Node_high_heap;

// 当我们重载了<后，我们在创建我们的数据结构是就只能使用上述形式，只能使用一个模版参数

• 我们自定义我们的比较函数

struct Node {
	int x, y;
};

struct cmp {
	bool operator() (const Node& a, const Node& b) {
		if(a.x == b.x) return a.y > b.y;
		return a.x > b.x;
	}
};

priority_queue<Node, vector<Node>, cmp> Node_high_heap;

• 同时我们也可以使用C11的形式进行书写

auto cmp = [](const pair<int, int>& a, const pair<int, int>& b) {
		if(a.x == b.x) return a.y > b.y;
		return a.x > b.x;
	};
priority_queue< pair<int, int>, 
		vector<pair<int, int>>, 
		decltype(cmp)> Pair_High_Heap(cmp);