优先队列:出队顺序和入队顺序无关,和优先级相关;
使用堆这种底层数据结构来实现优先队列,它的时间复杂度最好最坏都是O(log n ),极高的提高了性能
二叉堆
定义:使用二叉树实现的堆;
堆通常是一个可以被看做一棵完全二叉树的数组对象
二叉堆是一颗完全二叉树
特点:
- 堆中的某个结点的值总是不大于其父节点的值;(最大堆)
堆的时间复杂度
优先对列—自定义优先级
经典问题,时间复杂度
思路:每次遍历取出元素进行储存,需要剔除最小值,所以需要一个最小堆,取出最小值,剩下的堆就是我们需要的优先队列;
自定义优先级
自定义一个比较器
具体的函数实现
使用import java.util.PriorityQueue;
- 因为有比较器接口,直接实现,省去自定义
二叉堆的扩展:
d叉堆—-时间复杂度为logd(n)
索引堆和图论有关(了解)
二项堆和斐波那契堆(了解)
Other:
- leetcode第347题