Heap sort implementation with linked list and arrays

Question

Heap sort can be implemented using linked list and arrays.

What would be the ideal method of doing it-using linked list or arrays?

What is the time complexity to build heap using arrays and linked lists?Is it O(nlogn) for both?

What is the time complexity for deletion?

This looks an assignment: Please give your take for each of the questions raised. Where different from "conventional wisdom", show your reasoning. — greybeard
– greybeard, Commented Jan 31, 2018 at 7:49

songlj · Accepted Answer · 2013-01-29 13:45:12Z

2

for array, it is O(nlogn). becoz u can easily fetch element at index i. this characteristic makes it easy to fetch each node's parent and left/right child. and the time complexity for deletion is O(lgn).

for linked list, i think it is a different story. it depends how u define the "next" node. as far as i know, it is more complex than using array.

answered Jan 29, 2013 at 13:45

songlj

9371 gold badge6 silver badges10 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

sr01853 · Accepted Answer · 2013-01-29 13:52:25Z

2

Binary Heap

Time complexity in big O notation

        Average        Worst case
Space   O(n)           O(n)
Search  N/A Operation  N/A Operation
Insert  O(log n)       O(log n)
Delete  O(log n)       O(log n)

So, Time complexity is the same independent of whether it is using linked lists arrays .

answered Jan 29, 2013 at 13:52

sr01853

6,1491 gold badge21 silver badges39 bronze badges

Comments

user448810 · Accepted Answer · 2013-01-29 13:48:46Z

0

Time complexity is the same using either linked lists or arrays, assuming a proper implementation.

I have several implementations of heap sort at my blog. Start here for the traditional array-based version, then follow the links for several linked list versions.

answered Jan 29, 2013 at 13:48

user448810

17.9k4 gold badges38 silver badges61 bronze badges

1 Comment

greybeard Over a year ago

(Posts shall contain enough information to stay useful even when (external) hyperlinks go stale.) The presentation of heapify is bad. I neither found a single linked list versions (not even an explicit hyperlink) nor a complexity analysis.

Collectives™ on Stack Overflow

Heap sort implementation with linked list and arrays

3 Answers 3

Comments

Comments

1 Comment

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Linked

Related