堆
2025-06-21 20:07:39
发布于:上海
堆可被视为一颗完全二叉树。
堆在完全二叉树上加了性质:
1.大根堆:每个孩子节点小于等于其母亲节点
2.小根堆:每个孩子节点大于等于其母亲节点
对于左右孩子,其大小没有约束
有别于排序二叉树(左节点小于等于母亲节点小于等于右节点)
但不管是堆还是排序二叉树都是基于完全二叉树
存储可以使用结构体(struct)
存储完全二叉树:使用数组
编号为x的节点,在数组中下标为x的地方。
满足左儿子编号为母节点两倍,右儿子为左儿子加一
堆的操作:
1.加入元素
2.取出并删除元素
优先队列 是与堆有关的。
优先队列与队列 没有太大的关系。
priority_queue<int>pq;//定义
补充:一些有关反悔贪心的题目可以使用优先队列来进行处理
这里空空如也
有帮助,赞一个