将最大堆用于优先级队列的具体目的是什么

Question

Max堆用于优先级队列，因为便宜地提取了max元素。

但是，请容忍我。

我们不应该只搜索O（N）次的最大元素吗？

我知道要提取最大值，我们只需要O（log N）时间，但是在我们这样做之前，我们需要构建一个堆，而该堆本身需要O（N）时间。

那么，为什么我们还要经历这么多的复杂性甚至实现堆？

此外，有人可能会说执行重复提取最大堆是一个优点。

但是，假设我们执行了k次搜索操作，因此通过线性搜索，我们得到O（KN）== O（N），与堆O（N + K）== O（N）相同

如果执行N次提取，则得到的O（NLogN）优于（NN）==（N ^ 2）搜索操作。

但是我们也可以在O（NlogN）中对数组排序，然后在O（1）时间中有N个提取物==> O（NlogN）+ O（N）。

所以我的疑问是，我们真的需要堆吗？如果不是更好的方法，我们可以将堆的功能替换为非常相似的过程。

我缺少的是什么，真正用于堆的是什么。

请原谅我的无知和对语法的不好用法。不是母语人士，抱歉：（....

Answer 1

您可以使用堆以O（n log n）-时间对该数组进行排序在最坏的情况下（与Quicksort不同，除非您实施了一个不实际的复杂枢轴选择过程）和无需其他操作空格（与Mergesort不同，除非您实施不实际的[[at all复杂的就地合并）。

虽然当您混合插入和提取时，堆确实闪闪发光（例如，Dijkstra的算法，Prim的算法）。

Answer 2

考虑混合N插入和N提取的方案。

对于堆，您总共获得O(NlogN)个步骤。

对于简单的方法，您总共需要O(N^2)个步骤。

对于一种排序方法（在插入时在查询的末尾添加元素，您还可以获得O(N^2)总步骤。

Answer 3

考虑在现实世界中如何使用优先级队列。您添加了一些东西，带走了一些东西，添加了一些东西，提取了一些东西，等等。对于一个堆，在最坏的情况下，添加和删除都是O（log n）。对于列表，添加为O（1）或删除为O（1）。另一个是O（n）。通常，您希望Add为O（n），以便始终对列表进行排序，并且Peek操作可以为O（1）。

因此，给定一系列添加和删除操作，当堆中已经有1,000个项目时：

Operation     Heap    List
Add           log n     n
Add           log n     n
Remove        log n     1
Add           log n     n
Add           log n     n
Add           log n     n
Remove        log n     1
Remove        log n     1
Remove        log n     1
Remove        log n     1

对于堆来说是10 * log（n），对于列表来说是5n + 5。 log（n）为1,000时大约为10。因此，您要说的是对堆执行100次操作的顺序。对于列表，您正在谈论5,000次操作。因此，堆的速度将提高50倍。如果列表中有一百万个项目，那么您说的是一个堆的200个操作，一个列表的5个
million操作。
如果您只想按顺序浏览一堆项目，那么使用优先级队列实际上没有任何意义。排序列表可以很好地工作，并且可能比建立优先级队列和逐项提取项目要快。 （尽管您可能最终会使用堆排序对项目进行排序。）
使用正确的工具进行作业。