堆使用链接列表排序

Question

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

我也在使用C.

Answer 1

答案是"你不想在链表上实现堆排序."

Heapsort是一个很好的排序算法,因为它O(n log n)和它就位.但是,当你有一个链表时,heapsort不再O(n log n)是因为它依赖于对数组的随机访问,而你在链表中没有.所以你要么丢失你的就地属性(但需要定义树状结构就是O(n)空间).或者您将需要不使用它们,但请记住,链接列表O(n)用于成员查找.这使得运行时复杂性O(n^2 log n)变得比bubbleort更糟糕.

只需使用mergesort.您已经有了O(n)内存开销要求.