为什么不建议使用堆来对链表进行排序？

Question

我知道如何使用归并排序对链表进行排序。但问题是，为什么我们不使用堆来创建已排序的LinkedList呢？

1.遍历链表，并将项目添加到最小堆中。 2.从堆中取出项目，重新构建堆并添加到新的结果LinkedList中。

第一步需要O(n)的时间用于遍历列表和O(nlogn)的时间将项目添加到堆中。总共需要O(nlogn)的时间[如果我错了，请纠正我]。

从堆中获取一个项目的时间复杂度为O(1)，将项目作为下一个节点添加到LinkedList中的时间复杂度为O(1)。[如果我错了，请纠正我]

因此，如果我理解正确，这种排序可以在O(nlogn)的时间内完成。这与归并排序相同。就内存而言，我们使用了一个额外的堆，所以总内存可以是O(nlogn)。归并排序也可能需要O(nlogn)，但可以改进为O(logn)。

堆逻辑与“合并k个已排序链表”的逻辑相同。我假设每个链接列表都只有1项。

关于堆版本的时间复杂度，我的复杂度分析可能完全错误。如果有人知道为什么不能使用堆（为什么归并排序更好），请解释一下。这不是堆排序，也不是原地算法。如果时间复杂度是O(n²logn)，我不确定为什么。

- Sanish Joseph

---

我不是完全明白，但我认为你的意思是“枚举链表元素并将每个元素插入二叉树中。然后通过对树进行排序遍历来重构列表。这种方法没有任何问题，只是它不是归并排序。” - selbie

@selbie 是的，这就是想法。由于我有一个小根堆，我总是能得到最小值。在一本书中，我看到我们无法使用快速排序或堆排序对单向链表进行排序。所以我很好奇为什么我们不用堆来排序。虽然不如堆排序高效，但如果我的复杂度理解正确的话，也不比归并排序差。 - Sanish Joseph

你是在谈论为堆创建一个全新的、独立的结构吗？这样做需要额外编程时间，但并不能提高性能吗？ - JaMiT

“如果有人知道为什么不应该使用堆（heap）的确切原因”，那么谁说不应该使用它？出处在哪里？ - trincot

类别性的陈述，比如“不要使用堆来排序链表”，是完全错误的。 - paulsm4

没有人说堆不能被使用。他们说堆排序不能用于链表，因为它是原地排序。我只是好奇为什么不仅仅使用堆进行排序，因为据我理解，复杂度是相似的。 - Sanish Joseph

Answer 1

据我所知，并没有法律禁止使用堆对链表进行排序，但是请考虑以下几点：

- 使用相同的方法，您可以使用任何用于数组的排序算法：将列表的值复制到一个数组中；使用您喜欢的算法对数组进行排序，并从数组重新创建链表。 - 大多数涉及链表的代码挑战都不希望您使用任何其他O(n)数据结构，而只使用链表。根据挑战的要求，甚至可能需要仅使用O(1)辅助内存。 - 如果O(1)辅助内存是一个要求，则将链表转换为堆组织的链表不是实际可行的：它无法提供从节点到其堆子节点以及堆父节点的有效遍历。另一方面，其他高效的算法，如归并排序和某些快速排序，可以使用链表结构实现。

- trincot

---

是的，我同意。这类似于将所有元素添加到数组中并对其进行排序，然后从排序后的数组中将所有内容添加回链表中。在这种情况下，空间复杂度应该是O(n)。 - Sanish Joseph

Answer 2

问：为什么不用堆来创建已排序的LinkedList呢？ 答：有几个原因，其中之一是渐进复杂度并非唯一标准。对于链表而言，归并排序特别整洁高效，因此它是O(nlogn)链表排序中表现最佳的算法之一。此外，堆排序需要使用数组的索引关系来提供树的隐式表示形式，并通过O(1)辅助空间完成数组的排序。但是，在链表排序中，访问一个元素并不总是O(1)，这就需要将堆构建为实际的树形结构或者数组形式，这会带来O(n)的额外开销。此外，归并排序易于实现稳定性，但堆排序要想实现稳定性就比较困难，可能需要更多的开销。虽然在链表排序和堆排序中都需要O(nlogn)，但如果所有其他因素相同，链表归并排序的代码比堆排序简单得多，这意味着更快的开发和更少的错误。

在一本书中，我看到了这样一句话：使用快速排序或堆排序无法对单向链表进行排序。

即使我们不允许将链表读入辅助数组或其他数据结构来执行实际的排序，那本书也是错的。如果您禁止使用这样的辅助结构，则我认为您不能在少于 O(n^2 log n) 步骤内对单向链表执行堆排序，但是您确实可以进行排序。并且你并不需要快速随机访问或双向遍历来执行O(n log n) 快速排序。

- John Bollinger

---

很好的解释。我自己给原问题添加了一个回答，但是从您的答案中学到了很多。谢谢。 - user1984

Answer 3

将元素推入堆中和从堆中弹出元素都是对数操作。从堆中删除元素是对数的，因为堆需要调整其元素以保证堆不变量。因此，你需要做2*n*log n，虽然这在大O术语中仍然是线性对数级别，例如归并排序，但它可能会更慢。或者至少说，使用线性对数级别的排序算法比使用堆进行排序更好。

你可以做的是，将链表中的所有元素添加到堆的数据存储中，时间复杂度为O(n)，然后对其进行堆化，如果实现正确，则运行时间也为O(n)。然后你将有2n+n*log n，这可简化为O(n*log n)，具有更好的常数。

堆使用的额外空间不是O(n*log n)。它是线性的，虽然这取决于堆实现，但许多标准堆实现提供了这个特性。

当使用堆合并k个已排序链表时，你受益于k远小于列表长度本身的事实。这导致了一个O((n1+n2+...)*log k)算法，其中n1,n2,...是涉及的列表长度。如果不使用堆，则该算法将以O((n1+n2+...)*k)时间运行。

最终，如果堆被正确实现和使用，你将具有线性对数级别的时间复杂度和线性空间复杂度来对链表进行排序。但无论如何，其他变量相等，标准排序算法在排序方面具有更好的常数，除非有一些特殊要求和约束。让我重申一遍，两种方法在大O术语中都是线性对数级别，但排序算法可以针对这个特定目的具有更好的常数，在实际应用中可以意味着很多。原因是堆需要保证在任何时候以O(1)时间访问最小/最大元素。这会对其行为产生限制，你无法像标准排序算法那样对其进行优化。

- user1984