a*******g
发帖数: 1221 | 1 经常看到这个词，现实中也没见过。system design的时候一到关键地方就说这用
priority queue，但我到现在也没明白啥是priority queue。它到底是queue还是array
还是heap还是map。譬如给你45分钟写一个，那怎么写？ |
C*****n
发帖数: 1049 | |
W***o
发帖数: 6519 | |
a*******g
发帖数: 1221 | 4 你不知道就说不知道，不要装逼
【在 C*****n 的大作中提到】
: 等你有些编程经验了再回来自己回答这个问题吧
|
f*******t
发帖数: 7549 | |
o****o
发帖数: 35 | |
R*****i
发帖数: 2126 | 7 我也不知道priority queue究竟是个神马鬼东西，看了维基也不知所云，queue难道不
是已经有order了嘛？也许priority queue的每个元素还有另外一个属性构成了另一个
order，所以priority queue其实是一个queue 外加一个 sorted list? |
n**********r
发帖数: 43 | 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********s
发帖数: 1047 | |
b*j
发帖数: 33 | 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***s
发帖数: 117 | 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****7
发帖数: 1 | 12 Priority Queue是一个抽象数据结构，类似的一些应用有急诊室叫号，Queue是先进先
出，如果在急诊室，有些挂号需要加急处理，这时候就需要用到Priority Queue。一般
implemented用heap，heap自然用array，你非要用linkedlist也可以，但效率显然不如
array。 |
