`
kmplayer
  • 浏览: 509817 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

优先级队列

阅读更多
1,优先级队列是不同于先进先出队列的另一种队列。
最大优先级队列,是这样的一种队列结构,它的内部存放着一系列的元素,每个元素都对应着一个最优级,
最大优先级队列不管各元素的入队顺序,在出队时,总是对应优先级最大的元素出队。

2,优先队列是0个或多个元素的集合,每个元素都有一个优先权或值.
对优先队列执行的操作有1) 查找;2) 插入一个新元素;3) 删除.
在最小优先队列(min priority queue)中,查找操作用来搜索优先权最小的元素,删除操作用来删除该元素;
在最大优先队列(max priority queue)中,查找操作用来搜索优先权最大的元素,删除操作用来删除该元素.

3,。优先级队列一般分最大优先级队列和最小优先级队列
。这两种优先级队列只是为了适应不同场合的需要而进行区分实现,在算法上来讲没有什么本质的不同.

4,最大优先级队列一般用二叉树来实现。因为考虑到,对于最大优先级队列来讲,我们关心的只是最大值,因此,这时的二叉树只需要具备下面这个性质,那么就可以实现了:
性质A:总是让二叉树中的每一个节点的key(也就是优先级)值比该节点的子节点的key值大。
保持性质A就可以在每次出队操作时,直接取根节点得到最大优先级的元素。然后再进行树结构的调整,使得取出根节点之后,二叉树仍然保持性质A。
这样的二叉树可以保证,每个入队和出队的操作都在O(h)的时间内完成(h是树的高度)

5,考虑到这个树要保证的性质只有性质A,那么可以让这棵二叉树总是保持为完全二叉树(且不破坏性质A),这样树高就会是lgn,那么入队和出队操作的时间复杂度就是O(lgn)。这就比较理想了。

6,对于一棵完全二叉树,我们可以用数组(而不是链表)方式来实现。因为对于数组实现的完全二叉树,index为i的节点,它的父节点的index 是i/2,左子节点的index是i*2,右子节点的index是i*2+1。乘2和除2都是可以通过位移来实现的,效率上很好。而且通过保存元素个数,可以O(1)时间只找到处于树的最未的那个元素。用数组来实现还有一个好处,就是不需要在数据结构中再实现对父、子节点的指针存储,这样也省下了不少空间。这些特点都非常适合(也很好地改善了)优先级队列的实现。
分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics