2
$\begingroup$

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 ?

Improve this question
$\endgroup$
5
  • 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, 2018 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, 2018 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, 2018 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, 2018 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, 2019 at 9:33

1 Answer 1

Reset to default
-1
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • 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, 2019 at 9:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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