c - 使用链表进行堆排序

Question

我想知道是否有人曾经使用链表进行堆排序，如果他们可以提供代码。我已经能够使用数组进行堆排序，但尝试在链表中进行堆排序似乎不切实际，而且在你知道的地方只是一种痛苦。我必须为我正在做的项目实现链表，我们将不胜感激任何帮助。

我也在用C。

Answer 1

答案是“你不想在链表上实现堆排序。”

Heapsort 是一种很好的排序算法，因为它是 O(n log n) 并且是就地排序。但是，当您有一个链表时，堆排序不再是 O(n log n)，因为它依赖于对数组的随机访问，而这在链表中是没有的。所以你要么失去你的就地属性(需要定义一个树状结构是 O(n) 空间)。或者您将需要在没有它们的情况下进行操作，但请记住，链表对于成员查找而言是 O(n)。这使运行时复杂度达到类似 O(n^2 log n) 的程度，这比冒泡排序更糟糕。

只需使用归并排序即可。您已经有 O(n) 内存开销要求。