Heap sort using linked lists
c, heapsort, linked-list, sorting
Solution
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.
Problem
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.