优先队列(1)——API和初等实现

2016-04-29   |     |     |  

本系列文章主要介绍常用的算法和数据结构的知识,记录的是《Algorithms I/II》课程的内容,采用的是“算法(第4版)”这本红宝书作为学习教材的,语言是java。这本书的名气我不用多说吧?豆瓣评分9.4,我自己也认为是极好的学习算法的书籍。

通过这系列文章,可以加深对数据结构和基本算法的理解(个人认为比学校讲的清晰多了),并加深对java的理解。

优先队列的API和初等实现

做一个总结:

  • 栈 :先进后出
  • 队列 :先进先出
  • 随机队列 : 随机出
  • 优先队列: 每次出来的是最大值或最小值

优先队列的API

优先队列在很多场合都有用,
比如:在大量数据里,如果取前M大的数据(存储不足以存下如此大规模数据),就可以用优先队列(MinPQ来做,类似MaxPQ,只是每次删除最小值)——一直保证队列中只有M个比较大的数据,每次删除超过M个里面的最小值。

初等实现

如果用数组来做,我们可以考虑用排序好的数组或没排序的数组。

它们的实现方案都比较简单,但是都有致命的缺点:

排序数组,每次插入的时候需要N的时间复杂度
未排序的数组:每次删除或查找的时候,需要N的时间复杂度
我们的目标是找到一个插入和删除都logN复杂度的数据结构。——二叉堆