堆和优先队列

二叉堆只是优先队列的一种实现方式

二叉堆

二叉堆是一颗二叉树，而且是完全二叉树，每个结点中存有一个元素（或者说，有个权值）。

堆性质：父亲的权值不小于儿子的权值（大根堆）。

插入操作：最下一层最右边叶子之后插入（or新增一层）；向上调整，后，没有其他节点不满足二叉堆性质；向上调整复杂度为logn

删除操作：指删除最值元素。将根节点与最后一个节点直接交换；删除根节点；向上调整（在该节点的儿子中找最x的），后，…，复杂度…。

建堆操作：从一个空的堆开始，插入n个元素，nlogn

优先队列

std::priority_queue<TypeName> q; // 数据类型为 TypeName std::priority_queue<TypeName, Container> q; // 使用 Container 作为底层容器 std::priority_queue<TypeName, Container, Compare> q; // 使用 Container 作为底层容器，使用 Compare 作为比较类型// 默认使用底层容器 vector，比较类型 less<TypeName>（此时为它的 top() // 返回为最大值） 若希望 top() 返回最小值，可令比较类型为 greater<TypeName> // 注意：不可跳过 Container 直接传入 Compare

更具体例子：

priority_queue<int,vector<int>,greater<int>>q;//小根堆 priority_queue<int,vector<int>,less<int>>p; //大根堆

老生常谈上函数：

成员函数

常数复杂度：
·top访问堆顶元素(非空)

·empty()

·size()

对数复杂度：
·push(x) 插入并自动排序

·pop() 删除堆顶元素（非空）

需要注意的是函数top与pop的前提，此时优先队列不能为空；使用top访问堆顶元素，而非front

总结

以上是生活随笔为你收集整理的堆和优先队列的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。