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