Heap sort using linked lists

Question

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.

Also I am using C.

Answer 1

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

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.

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