Heap sort using linked lists

c sorting linked-list heapsort
Lane Fujikado picture Lane Fujikado · Jun 4, 2012 · Viewed 27.3k times · Source

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

OmnipotentEntity picture OmnipotentEntity · Jun 4, 2012

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.

Related questions

Sorting a linked list in C

I'm trying to sort a linked list by finding the largest value, deleting it from its position, and then inserting it at the top of the list. The difficulty I'm running into is the actual deleting and inserting at the …

Read More
C library function to perform sort

Is there any library function available in C standard library to do sort?

Read More
How to sort an array of string alphabetically (case sensitive, nonstandard collation)

I need a c language code to sort some strings and it should be case sensitive and for the same letter in upper- and lower-cases, the lower-case must come first. For example the result of the sort for the following …

Read More