注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

I choose

sailing with my heart ......

 
 
 

日志

 
 

堆与优先级队列  

2010-05-24 14:18:38|  分类: 笔试题库 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

优先级队列是一种数据结构,其中能被访问和删除的是仅具有最高优先级的元素。所谓优先级是通过一些方法对元素进行比较得出的。基本的思路是队列中存在等待服务的元素。对元素的选取不再严格基于先来先服务原则。


定义如下:优先级队列是这样的一种数据结构,对它的访问或者删除操作只能对集合中通过指定优先级方法得出的最高优先级元素进行。


优先级队列是公平的,对于任何两个具有相同优先级的元素,首先被删除的是那个在队列中存在时间最长的元素。如果元素是Integer类型且按照其排列的顺序进行比较,那么具有最高优先级的元素就是优先级队列中相应的int值最小的那个元素。如果元素是Integer类型,但是比较方法与原排列顺序相反,那么具有最高优先级的元素就是优先级队列中相应的int值最大的元素。到底是最小的还是最大的元素优先,具体的优先比较算法由实现PriorityQueue接口的程序员来决定。


那么堆与优先级队列又有什么关系呢,实质上堆可用来实现优先级队列,或者说堆就是一种优先级队列。由于堆的添加元素与删除元素时都会破坏堆结构,所以添加与删除进都要进行结构调整。一般普通的队列添加是在最后加入,但优先级队列却不一定添加到最后,他会按照优先级算法把它插入到队列当中去,出队时还是从第一个(也即最小元素,优先级最高)开始,即取根元素,这样保证了队列中优先级高的先服务,而不是先来先服务了。

Heap类是对PriorityQueue接口的一种高效实现。堆是一种完全二叉树。由于使用基于数组的完全二叉树的表示,可以根据子节点的索引快速计算出你父节点的索引,反之亦然,所以,使用数组来表示堆,它是利用了数组可以根据给定索引随机访问元素的特性。

工具软件下载请到馒头软件:http://www.mantoo.com.cn
  评论这张
 
阅读(625)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017