CODEWITHSUNDEEP
java
Aristotelis
Aristotelis

Reputation: 21

Time complexity of a max heap remove

In java I have a city object where each city has an ID and its population. I have to create a max heap based on the population and then create a remove method where I can remove a city object from anywhere in the heap based on a given ID.

I am going to implement the method my swapping the object I want to remove with the last object and then removing the last object and heapifying the object in the position where the object I wanted to delete was. My question is: What is the time complexity of such a method? I want it to be O(logn) but I don't think that's the one. Do you have any ideas? Maybe I should store the ID on another array or something like that? (I am not allowed to use any kind of the implementations for a heap java already has)

Thanks in advance for helping

Upvotes: 2

Views: 286

Answers (1)

Chukwuemeka Onyenezido
Chukwuemeka Onyenezido

Reputation: 349

If you need to remove from the heap based on the City id this means you have to search for the id.

There are essentially 2 options;

  1. Search for the ids in the heap. O(N) search
  2. Maintain the ids and heap index in another structure and retrieve them from there. O(1) search

For option 1, you can easily traverse your heap and check for the id you are looking for.

For option 2, you can insert the id and the corresponding heap index in a simple map (eg HashMap) and then you can easily retrieve them if you wish.

Upvotes: 1

Related Questions