什么是最小优先级队列

显示全部楼层 · 2016-7-1 22:26:54

优先队列又叫做堆，分最小堆和最大堆，你说的最小优先队列就是最小堆这个是一种二叉树，最小堆的主要性质是每一棵子树的根结点的值都要比他的儿子的要小。每次从这个堆是取一个最小的和插入一个值并把堆调整成最小堆的花费都log2(n)级别的。这个在时间排序调度算法上有很好的应用。这个东西是很有用的。经常和一些其他的算法结合在一起使用。比如我们动态的给出一些数字，或者删除一些数字，然后询问当前的数字中的中位数是多少。或者动态的插入删除数字，问当前数字中最小值是多少。等等...

千问 · 2016-7-1 22:26:54

队列有优先级，最小优先级就是优先级最小的队列，没什么用...

千问 · 2016-7-1 22:26:54

将每个元素配一个优先级标识，最小标识标识优先级最高（相当于队列的头），优先级高的元素优先享有查找、删除。最典型的就是二叉堆。...