# Building heaps and heapsort using linked list

I know that linked list is not a appropriate data structure for building heaps but I am interested in knowing the time complexity of building heaps and heapsort using linked list.

One of the answers here (https://stackoverflow.com/a/14584517/5841727) says that heap sort can be done in O(nlogn) using linked list which is same as with arrays.

For building a heap, I think that heapify operation would cost O(n) time in linked list and we would need (n/2) heapify operations leading to time complexity of O(n^2). Is it correct?

Also, can someone please tell how to achieve O(nlogn) complexity (for heap sort ) using linked list ?

• Possible duplicate of Show that the running time of the build_heap function is $O(n)$: You can check the analysis given at this link to see that both with a linked list as an array we can build a heap in $O(n)$. Feb 1, 2018 at 10:29
• @Discretelizard I know the derivation of complexity using arrays. I am just not sure about linked list as linked list doesn't support random access. Feb 1, 2018 at 11:54
• Well, a good start would be to look at that derivation and see whether random access is used at all. If you find where, add that to this question to clarify. Otherwise, you're done! Feb 1, 2018 at 14:29
• @Discretelizard In heapify function, you need random access. In case of arrays, you can access a[2i] and a[2i+1] directly but in linked list, you need to traverse till that index sequentially to access those values (left and right siblings). Feb 1, 2018 at 14:34
• we would need (n/2) heapify operations No. In heap-sort, heapify is used once, followed by more sifts in the opposite direction.. Nov 9, 2019 at 9:33

## 1 Answer

doubly linked list can be sorted by heapsort with O(nlogn) time, O(1) space complexity, but not singly linked-list. merge sort can apply to singly linked list with O(nlogn) time, O(n) space complexity.

• This answer would be greatly improved by explanations of how this is done, why it can't be done for singly-linked lists and, ideally, giving some citations. Jun 12, 2019 at 9:03