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 ?
we would need (n/2) heapify operationsNo. In heap-sort, heapify is used once, followed by more sifts in the opposite direction.. $\endgroup$