The only example of using the priority queue I know of, is the Dijkstra's Algorithm (for calculating minimum cost)
使用我所知道的优先级队列的唯一例子是Dijkstra算法(用于计算最低成本)
In what other situations would it be useful?
在其他情况下它会有用吗?
5 个解决方案
#1
39
Here's a practical example - for a business application:
这是一个实际的例子 - 对于业务应用程序:
You're running a hospital and patients are coming in. There's only one doctor on staff. The first man walks in - and he's served immediately. Next, a man with a cold comes in and requires assistance. You add him to the queue and he waits in line for the doctor to become available. Next, a man with an axe in his head comes through the door. He is assigned a higher priority because he has a higher medical liability. So the man with the cold is bumped down in line. Next, someone comes in with breathing problems. So, once again, the man with the cold is bumped down in priority. This is called triaging in the real world - but in this case it's a medical line.
你正在经营一家医院,病人正在进来。工作人员只有一名医生。第一个男人走了进来 - 他马上就服完了。接下来,感冒的男人进来需要帮助。你将他加入队列,他排队等候医生可用。接下来,一个头上戴着斧头的男人穿过门。他被赋予更高的优先权,因为他有更高的医疗责任。所以患感冒的男子排成一列。接下来,有人有呼吸问题。因此,患有感冒的男子再次受到优先考虑。这在现实世界中被称为分类 - 但在这种情况下,它是一条医疗线。
Implementing this in code would use a priority queue and a worker thread (the doctor) to perform work on the consumable / units of work (the patients)
在代码中实现这一点将使用优先级队列和工作线程(医生)来执行消耗品/工作单元(患者)的工作
#2
9
Scanning through a large collection of statistics to report the top N items - N busiest network connections, N most valuable customers, N largest disk users...
扫描大量统计数据以报告前N项 - N个最繁忙的网络连接,N个最有价值的客户,N个最大的磁盘用户......
#3
7
A priority queue based on a heap is partially sorting the input sequence. This has advantages over straight away sorting it when you don't need the whole sequence, as mcdowella gave a few examples for. In particular, if you only need m of the n elements, you have O(m log n) complexity. A second advantage is when you are dynamically adding elements, i.e. when you don't know the whole sequence in advance. With the heap as backing storage, adding another element is faster than inserting it into a sorted sequence.
基于堆的优先级队列部分地对输入序列进行排序。当你不需要整个序列时,这比直接排序它有优势,因为mcdowella给出了一些例子。特别是,如果您只需要n个元素中的m个,则具有O(m log n)复杂度。第二个优点是当您动态添加元素时,即当您事先不知道整个序列时。使用堆作为后备存储,添加另一个元素比将其插入已排序的序列更快。
Further, when you are popping single elements in a sorted order and then discard them (i.e. you don't need the sorted sequence afterwards), using a priority queue gives the reader the right message. It also makes it rather easy to swap different implementations, e.g. one based on a heap or one that sorts the input sequence in advance. This is a question of taste though, you can always achieve the same using any sequence that you then use accordingly, but this only makes the code more difficult to read.
此外,当您按排序顺序弹出单个元素然后丢弃它们时(即之后不需要排序的序列),使用优先级队列会为读者提供正确的消息。它还可以很容易地交换不同的实现,例如一个基于堆或一个预先对输入序列进行排序的。这是一个品味问题,你可以使用随后使用的任何序列来实现相同的效果,但这只会使代码更难以阅读。
#4
4
Here is the list:Event-driven simulation: customers in a line, colliding particles
以下是列表:事件驱动的模拟:一行中的客户,碰撞粒子
Numerical computation. reducing roundoff errorData compression. Huffman codes which compresses data.Graph searching:Dijkstra's algorithm, Prim's algorithmNumber theory: sum of powersArtificial intelligence: A* searchStatistics: maintain largest M values in a sequenceOperating systems: load balancing, interrupt handlingDiscrete optimization. bin packing, schedulingSpam filtering. Bayesian spam filter
数值计算。减少舍入误差数据压缩。压缩数据的霍夫曼码。图搜索:Dijkstra算法,Prim算法数理论:幂之和人工智能:A * searchStatistics:在序列中保持最大M值操作系统:负载均衡,中断处理离散优化。 bin packing,schedulingSpam过滤。贝叶斯垃圾邮件过滤器
#5
1
There are many applications of Priority queue (Min/max heap). But if you're looking for classical and famous algorithms, Prim's algorithm for an example, uses priority queue.
优先级队列(最小/最大堆)有许多应用程序。但是如果你正在寻找经典和着名的算法,Prim的算法就是一个例子,它使用优先级队列。
#1
39
Here's a practical example - for a business application:
这是一个实际的例子 - 对于业务应用程序:
You're running a hospital and patients are coming in. There's only one doctor on staff. The first man walks in - and he's served immediately. Next, a man with a cold comes in and requires assistance. You add him to the queue and he waits in line for the doctor to become available. Next, a man with an axe in his head comes through the door. He is assigned a higher priority because he has a higher medical liability. So the man with the cold is bumped down in line. Next, someone comes in with breathing problems. So, once again, the man with the cold is bumped down in priority. This is called triaging in the real world - but in this case it's a medical line.
你正在经营一家医院,病人正在进来。工作人员只有一名医生。第一个男人走了进来 - 他马上就服完了。接下来,感冒的男人进来需要帮助。你将他加入队列,他排队等候医生可用。接下来,一个头上戴着斧头的男人穿过门。他被赋予更高的优先权,因为他有更高的医疗责任。所以患感冒的男子排成一列。接下来,有人有呼吸问题。因此,患有感冒的男子再次受到优先考虑。这在现实世界中被称为分类 - 但在这种情况下,它是一条医疗线。
Implementing this in code would use a priority queue and a worker thread (the doctor) to perform work on the consumable / units of work (the patients)
在代码中实现这一点将使用优先级队列和工作线程(医生)来执行消耗品/工作单元(患者)的工作
#2
9
Scanning through a large collection of statistics to report the top N items - N busiest network connections, N most valuable customers, N largest disk users...
扫描大量统计数据以报告前N项 - N个最繁忙的网络连接,N个最有价值的客户,N个最大的磁盘用户......
#3
7
A priority queue based on a heap is partially sorting the input sequence. This has advantages over straight away sorting it when you don't need the whole sequence, as mcdowella gave a few examples for. In particular, if you only need m of the n elements, you have O(m log n) complexity. A second advantage is when you are dynamically adding elements, i.e. when you don't know the whole sequence in advance. With the heap as backing storage, adding another element is faster than inserting it into a sorted sequence.
基于堆的优先级队列部分地对输入序列进行排序。当你不需要整个序列时,这比直接排序它有优势,因为mcdowella给出了一些例子。特别是,如果您只需要n个元素中的m个,则具有O(m log n)复杂度。第二个优点是当您动态添加元素时,即当您事先不知道整个序列时。使用堆作为后备存储,添加另一个元素比将其插入已排序的序列更快。
Further, when you are popping single elements in a sorted order and then discard them (i.e. you don't need the sorted sequence afterwards), using a priority queue gives the reader the right message. It also makes it rather easy to swap different implementations, e.g. one based on a heap or one that sorts the input sequence in advance. This is a question of taste though, you can always achieve the same using any sequence that you then use accordingly, but this only makes the code more difficult to read.
此外,当您按排序顺序弹出单个元素然后丢弃它们时(即之后不需要排序的序列),使用优先级队列会为读者提供正确的消息。它还可以很容易地交换不同的实现,例如一个基于堆或一个预先对输入序列进行排序的。这是一个品味问题,你可以使用随后使用的任何序列来实现相同的效果,但这只会使代码更难以阅读。
#4
4
Here is the list:Event-driven simulation: customers in a line, colliding particles
以下是列表:事件驱动的模拟:一行中的客户,碰撞粒子
Numerical computation. reducing roundoff errorData compression. Huffman codes which compresses data.Graph searching:Dijkstra's algorithm, Prim's algorithmNumber theory: sum of powersArtificial intelligence: A* searchStatistics: maintain largest M values in a sequenceOperating systems: load balancing, interrupt handlingDiscrete optimization. bin packing, schedulingSpam filtering. Bayesian spam filter
数值计算。减少舍入误差数据压缩。压缩数据的霍夫曼码。图搜索:Dijkstra算法,Prim算法数理论:幂之和人工智能:A * searchStatistics:在序列中保持最大M值操作系统:负载均衡,中断处理离散优化。 bin packing,schedulingSpam过滤。贝叶斯垃圾邮件过滤器
#5
1
There are many applications of Priority queue (Min/max heap). But if you're looking for classical and famous algorithms, Prim's algorithm for an example, uses priority queue.
优先级队列(最小/最大堆)有许多应用程序。但是如果你正在寻找经典和着名的算法,Prim的算法就是一个例子,它使用优先级队列。