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 ?

  • 1
    $\begingroup$ 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)$. $\endgroup$ – Discrete lizard Feb 1 '18 at 10:29
  • 1
    $\begingroup$ @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. $\endgroup$ – Zephyr Feb 1 '18 at 11:54
  • 1
    $\begingroup$ 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! $\endgroup$ – Discrete lizard Feb 1 '18 at 14:29
  • 2
    $\begingroup$ @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). $\endgroup$ – Zephyr Feb 1 '18 at 14:34
  • $\begingroup$ we would need (n/2) heapify operations No. In heap-sort, heapify is used once, followed by more sifts in the opposite direction.. $\endgroup$ – greybeard Nov 9 '19 at 9:33

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.

  • 5
    $\begingroup$ 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. $\endgroup$ – David Richerby Jun 12 '19 at 9:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.