0

In data-structure course , I need to implement a binary heap with the following time - complexity requirements: Find Max - O(1) Insert - O(log n) Delete Max - O(log n)

Now I thought to implement this using array in the following way: The root of the heap is in Arr[1] (the first index). the childrens Arr[i] are in Arr[2i] and arr[2i+1] (2 childrens). With this implementation I will get Find Max in O(1) , Delete Max in O(log n) and insert in O(log 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 array but insert will still be O(n). Any suggestions for implenetation will be very welcome. Thank you in advance, Noam

Noam
  • 853
  • 4
  • 16

1 Answers1

0

You can't use arrays because like you said, resize an array will cost you O(n). But what you can do is to use Binary Tree is the most intuitive way to implement a Heap. Now you must remember that LinkedList and Binary Tree are two completely different things. Binary Tree is not made with LinkedList, but each data structure has its own special Node object. Binary Tree Nodes will contain the fields: Right, Left and data. (in LinkedList you create Node that have the fields: next and data). Your Binary Tree structure that you use for your Heap - his functions must be implemented with recursion. Hope I helped, feel to ask more.

LiziPizi
  • 2,855
  • Thank you but I don't understand excatly what do you mean. In my understanding a Binary tree is also an ADT that should be implemented in some way - for instance, using array. A heap is also an ADT which is private case of Binary tree where all nodes are in use except for maybe the right node in the buttom row. Can you explain in more details what do you mean as I'm kind of new to this whole subject. You compared between LinkedList and Binary Tree but in my understanding these aren't comperable because LinkedList is an implementation while Binary Tree is ADT , please correct me if I'm wrong. – Noam Apr 16 '16 at 17:25
  • any comment LiziPizi? – Noam Apr 18 '16 at 14:20