Implementation of Heap (ADT) using Array Vs. LinkedList

Question

In my data-structure course, I need to implement a binary heap with the following time - complexity requirements:

Find Max - O(1)
Insert - O(lg n)
Delete Max - O(lg n)

Now I thought to implement this using an array in the following way: The root of the heap is in Arr[1] (the first index). The children of Arr[i] are in Arr[2i] and Arr[2i+1] (2 children). With this implementation I will get Find Max in O(1), Delete Max in O(n) and insert in O(lg n) with an exception - if I need to insert when the array is full I will have to resize the array and will "cost" me O(n) so the total cost of insert with all edge cases will be O(n) instead of O(log n) as required.

Is there other way of implementation that answers all the complexisty requirements? I thought maybe to try to implement with a LinkedList instead of an array but insert will still be O(n). Any suggestions for an implementation will be very welcome.

Luke LaFountaine · Accepted Answer · 2016-04-15 19:22:13Z

1

Your implementation can satisfy the requirements. I assume that when you say delete max will take O(n), you are thinking that you need to shift the entire array over one position? What you actually need to do in that case is have have the next largest element 'swim' to the top as they say. This only requires O(lgn) time.

Also the resizing does not happen often so the amortized runtime is still O(lgn). See here.

edited Apr 15, 2016 at 19:22

answered Apr 15, 2016 at 19:16

Luke LaFountaine

8681 gold badge6 silver badges18 bronze badges

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

3 Comments

Noam Over a year ago

Thank you actually I meant to write that "delete max" is O(log n) by using the 'swim' technic you mentioned. My problem is with the Insert - I know that the amortized runtime is O(log n) but I need the worst-case run time to be O(log n) and that what makes me think that maybe I shouldnt implement this heap using array but in a different way...

Luke LaFountaine Over a year ago

Ok I see. One thought taken from that wikipedia article The motivation for amortized analysis is that looking at the worst-case run time per operation can be too pessimistic. I think you have the correct implementation. See this powerpoint. Your current implementation is still considered to be O(lgn).

Noam Over a year ago

Alright. so I'll probebly leave the implementation like this. Thank you

Collectives™ on Stack Overflow

Implementation of Heap (ADT) using Array Vs. LinkedList

1 Answer 1

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related