到底什么是priority queue啊？ - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

到底什么是priority queue啊？

到底什么是priority queue啊？# JobHunting - 待字闺中

a*g2016-11-23 08:11

1 楼

经常看到这个词，现实中也没见过。system design的时候一到关键地方就说这用
priority queue，但我到现在也没明白啥是priority queue。它到底是queue还是array
还是heap还是map。譬如给你45分钟写一个，那怎么写？

C*n2016-11-23 08:11

2 楼

等你有些编程经验了再回来自己回答这个问题吧

W*o2016-11-23 08:11

3 楼

其实pq就是heap的马甲

a*g2016-11-23 08:11

4 楼

你不知道就说不知道，不要装逼

【在 C*****n 的大作中提到】

: 等你有些编程经验了再回来自己回答这个问题吧

f*t2016-11-23 08:11

5 楼

https://en.wikipedia.org/wiki/Priority_queue

o*o2016-11-23 08:11

6 楼

挖坑的吧

R*i2016-11-23 08:11

7 楼

我也不知道priority queue究竟是个神马鬼东西，看了维基也不知所云，queue难道不
是已经有order了嘛？也许priority queue的每个元素还有另外一个属性构成了另一个
order，所以priority queue其实是一个queue 外加一个 sorted list?

n*r2016-11-23 08:11

8 楼

Priority Queue就是有Priority的Queue（废话）。它是Heap在Java语言里的具体实现
。不同语言里对Heap的实现类名不同，也稍有区别。在C#里，类似的是
SortedDictionary(Dictionary是类似Java里的HashMap)。在JavaScript里，就要自己
实现或用第三方的库了。比如http://www.collectionsjs.com/heap
Java里如果不是让你自己实现PriorityQueue的话，直接拿来用就可以了。它默认实现
了最小堆，如果要用最大堆，需要定义一个Comparator，实现compare方法。如果自己
实现的话，实现的方式可以有很多种。具体就看看Heap的定义吧。

u*s2016-11-23 08:11

9 楼

就是java里的heap

b*j2016-11-23 08:11

10 楼

反了，在Java库里面Priority Queue是用Heap来实现的。

【在 n**********r 的大作中提到】

: Priority Queue就是有Priority的Queue（废话）。它是Heap在Java语言里的具体实现
: 。不同语言里对Heap的实现类名不同，也稍有区别。在C#里，类似的是
: SortedDictionary(Dictionary是类似Java里的HashMap)。在JavaScript里，就要自己
: 实现或用第三方的库了。比如http://www.collectionsjs.com/heap
: Java里如果不是让你自己实现PriorityQueue的话，直接拿来用就可以了。它默认实现
: 了最小堆，如果要用最大堆，需要定义一个Comparator，实现compare方法。如果自己
: 实现的话，实现的方式可以有很多种。具体就看看Heap的定义吧。

b*s2016-11-23 08:11

11 楼

很简单，queue的意思是先进先出，priority queue也是进进出出，
不过它是找到那最最小的，先出
然后为了找最小的，用的heap来做，
而在代码里heap用一个array来表示，如果array的index从1开始的话，index i 的子节
点是 2*i 和 2*i + 1
45分钟很够了
然后，比如top k的问题，大概就是去出 k 次的意思，不过每一次出都要一个 logn 的
时间
如果赶时间，我会考虑先对top k排序，然后数据修改/添加的时候过一下heap

array

【在 a*******g 的大作中提到】

: 经常看到这个词，现实中也没见过。system design的时候一到关键地方就说这用
: priority queue，但我到现在也没明白啥是priority queue。它到底是queue还是array
: 还是heap还是map。譬如给你45分钟写一个，那怎么写？

c*72016-11-23 08:11

12 楼

Priority Queue是一个抽象数据结构，类似的一些应用有急诊室叫号，Queue是先进先
出，如果在急诊室，有些挂号需要加急处理，这时候就需要用到Priority Queue。一般
implemented用heap，heap自然用array，你非要用linkedlist也可以，但效率显然不如
array。