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 ?

asked Feb 1, 2018 at 2:40
$\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$ Commented 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$ Commented 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$ Commented 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$ Commented 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$ Commented Nov 9, 2019 at 9:33

1 Answer 1

-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.

answered Jun 12, 2019 at 8:00
$\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$ Commented Jun 12, 2019 at 9:03

Your Answer

Draft saved
Draft discarded

Sign up or log in

Sign up using Google
Sign up using Email and Password

Post as a guest

Required, but never shown

Post as a guest

Required, but never shown

By clicking "Post Your Answer", you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.