优先队列的目的是什么,当存在堆(heaps)时呢?

huangapple go评论67阅读模式
英文:

What is the purpose of a priority queue when heaps exist?

问题

我知道优先队列倾向于使用堆,但是当它们基本上与堆看起来相同时,优先队列的意义是什么?起初我以为所有优先队列都使用哈希映射来跟踪堆中所有对象的位置,从而更容易地查找、更新/删除这些对象。然而,我使用过Java的优先队列,你必须手动迭代它以更新或删除非位于根部的对象。优先队列看起来似乎只是一个堆,除此之外似乎没有什么特别之处,这似乎有些奇怪。

英文:

I know priority queues tend to use heaps but what is the point of a priority queue when they basically seem the same as heaps? I initially thought all priority queues use hash maps to keep track of all object's locations in the heap, making finding and updating/deleting said object easier. However, I have used Java's priority queue and you have to manually iterate over it to update or delete objects not at the root. It seems odd to have a priority queue that appears to literally just be a heap with nothing else special about it.

答案1

得分: 2

这里可能通过类比来进行推理会有帮助:

> List 相当于动态数组,正如 PriorityQueue 相当于二叉堆。

也就是说,列表(一系列从位置零开始的项目,可以插入和移除项目)的抽象概念是一个很好的高级概念,而动态数组(数组以及在需要额外空间时容量加倍或增加 1.5 倍)是实现列表的一种可能方式。如果你正在使用列表,你可以只考虑“哦,这是一个序列,我可以把东西放在某些地方”,而不必担心这个序列实际上是如何表示的。另一方面,使用动态数组需要你跟踪哪些数组元素是有效的,哪些元素实际上没有被使用,当没有更多空间时你需要手动转移元素,并仔细考虑增长策略等。这里的区别在于你从哪个层次来看待问题。如果你只需要“一个序列”,考虑“列表”。如果你需要从头开始构建一个表示序列的类型,考虑“动态数组”。

基本上,这就是优先队列与二叉堆的区别。优先队列抽象地表示了“我可以放入元素,它们将按排序顺序返回”的思想。二叉堆是一种实现优先队列的特定方式之一。在处理抽象优先队列时,你可以把思维集中在诸如“我想要添加哪些元素?”和“如何对它们进行排名?”等问题上。在处理二叉堆时,你必须考虑诸如“我是否使用从一开始计数还是从零开始计数?”和“如何通过索引 k 找到节点的子节点?”等问题。如果你只需要能够将元素放入一个袋子中并按排序顺序取出它们,你可以使用优先队列,而不必担心它的工作原理。如果你需要从头开始构建一个优先队列,你可以使用二叉堆。

回到列表与动态数组的类比中:有许多类型可以用来表示列表。动态数组是其中之一,但你也可以使用循环缓冲(适用于从末尾添加或删除的情况)或链表(适用于在列表之间移动项目的情况)。同样,有许多方法可以实现优先队列。二叉堆是一个选项,但还有配对堆、二项式堆等。保持相关的抽象关注点 - 我只需要一系列项目,我只需要一种按排序顺序检索项目的方法 - 意味着当你关心的是你想要执行的操作时,你不需要过多担心事物是如何工作的。

英文:

It might help to reason by analogy here:

> List is to dynamic array as PriorityQueue is to binary heap.

That is, the abstract idea of a list (a sequence of things starting at position zero where items can be inserted and removed) is a nice, high-level concept, while a dynamic array (an array along with a capacity that doubles or 1.5x’s in size if extra space is needed) is one possible way of implementing a list. If you’re using a list, you can just think “oh, it’s a sequence, and I can put things places” without worrying how that sequence is actually represented. On the other hand, working with a dynamic array requires you to track which array elements are valid versus which ones don’t actually get used, you need to manually transfer things over when there’s no more space and think carefully about your growth strategy, etc. The distinction here is at what level you’re viewing things. If you just need “a sequence,” think “list.” If you need to build a type from scratch representing a sequence, think “dynamic array.”

This is basically what’s going on with priority queues versus binary heaps. A priority queue abstractly represents the idea of “I can put things in and they’ll come back in sorted order.” A binary heap is one specific possible way of implementing a priority queue. When working with an abstract priority queue, you can focus your thoughts purely on questions like “what elements do I want to add?” and “how do I rank them?” When working with a binary heap, you have to think about things like “do I use one-indexing or zero indexing?” and “what’s the formula for identifying the children of a node at index k?” If all you need is the ability to put things in a bag and take them out in sorted order, you can use a priority queue without worrying about how it works. If you need to build one from scratch, you can use a binary heap.

Going back to the list versus dynamic array analogy: there are many types you can use to represent lists. Dynamic arrays are one, but you could also use a circular buffer (good if you add or remove from the ends) or a linked list (good if items get moved around between lists). Similarly, there are many ways you can implement a priority queue. Binary heaps are one option, but there’s also pairing heaps, binomial heaps, etc. Keeping the relevant abstraction in focus - I just want a sequence of things, I just want a way to retrieve things in sorted order - means that you don’t need to worry as much about how things work when what you care about is what operations you want to do.

答案2

得分: 0

个人观点,你是对的,Java的PriorityQueue是堆。作为一种高级编程语言,Java提供了所有常见和标准的算法实现是合理的,大多数时候我们关注业务逻辑的开发以及如何更快地完成工作。因此,我们不希望在从头开始构建优先队列时花费太多时间,此外,自行构建往往会很繁琐且容易出错。
如果你想要在同时更新或删除对象,并且不想手动遍历它,你可以这样做:

Object updatedObject;
priorityQueue.add(priorityQueue.remove(updatedObject));

虽然在更新频繁发生时效率可能不够高,但有一种叫做斐波那契堆的替代算法可以更好地完成这项工作:

英文:

Personal opinion, you are right, Java's PriorityQueue is heap. Java as a high level programming language, it is reasonable for it to provide all the common and standard algorithm implementations, most of the time we focus on business logic development and how to get the job done faster. So we don't want spend too much time on building a priority queue from the ground up, besides it is tedious and error-prone to do it yourself.
If you want update or delete objects at the same time, and don't want to iterate over it manually, you can just do this:

Object updatedObject;
priorityQueue.add(priorityQueue.remove(updatedObject));

although it's not efficient enough when updating occurs frequently, there is an alternative algorithm called Fibonacci heap to do the job better:

答案3

得分: 0

> 似乎有点奇怪,拥有一个看起来只是一个堆,没有任何其他特殊之处的优先级队列。

为什么?

名为PriorityQueue的内容并未承诺任何超出能够将项目放入一端并按优先级顺序从另一端取出的能力。这基本上也是堆的定义,这就是为什么堆是实现优先级队列的理想数据结构。

因此,实际上,Java集合框架的设计者实现了一个堆。只是他们没有称其为Heap,而是称其为PriorityQueue。故事结束。就像歌词中唱的:“谁还能要求更多呢?”

英文:

> It seems odd to have a priority queue that appears to literally just be a heap with nothing else special about it.

Why?

Nothing about the name PriorityQueue promises anything more than the ability to put items in one end and get them out the other in sorted-by-priority order. That's also basically the definition of a heap, which is why a heap makes an ideal data structure to implement a priority queue.

So, essentially, the Java Collections Framework designers implemented a heap. Only instead of calling it a Heap, they called it a PriorityQueue. End of story. As the song lyric goes: "Who could ask for anything more?"

答案4

得分: -1

Java的优先队列可以是最小堆或最大堆,根据构建方式的不同,它总是会返回最小值或最大值。

英文:

Java's Priority queue is can be either a min Heap or a max Heap, and based on how you have constructed it, it will always give you the min/max value.

huangapple
  • 本文由 发表于 2020年9月10日 10:56:45
  • 转载请务必保留本文链接:https://go.coder-hub.com/63822165.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定