使用链表进行堆排序 [英] Heap sort using linked lists

问题描述

我想知道是否有人使用过链表进行堆排序，是否可以提供代码.我已经能够使用数组进行堆排序，但是尝试在链表中执行它似乎不切实际，而且在您所知的地方也很痛苦.我必须为我正在做的项目实现链接列表，任何帮助将不胜感激.

I was wondering if anyone has ever used linked lists to do heap sort and if they have could they provide the code. I have been able to do heapsort using arrays, but trying to do it in linked lists seems unpractical and just a pain in the you know where. I have to implement linked lists for a project Im doing, any help would be greatly appreciated.

我也在用C.

推荐答案

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

The answer is "you don't want to implement heap sort on a linked list."

堆排序是一种很好的排序算法，因为它是O(n log n)并且就地.但是，当您有一个链表时，heapsort不再是O(n log n)，因为它依赖于对数组的随机访问，而您不在链表中.因此，您要么失去了就地属性(通过定义树状结构为O(n)空间)，要么就失去了就位属性.否则，您将不需要它们，但是请记住，对于成员查找，链接列表为O(n).这使运行时复杂度达到O(n^2 log n)之类的水平，比冒泡的情况更糟.

Heapsort is a good sorting algorithm because it's O(n log n) and it's in-place. However, when you have a linked list heapsort is no longer O(n log n) because it relies on random access to the array, which you do not have in a linked list. So you either lose your in-place attribute (by needing to define a tree-like structure is O(n) space). Or you will need to do without them, but remember that a linked list is O(n) for member lookup. Which brings the runtime complexity to something like O(n^2 log n) which is worse than bubblesort.

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

Just use mergesort instead. You already have the O(n) memory overhead requirement.

这篇关于使用链表进行堆排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！