In java Implement a generic min heap class and write a test code to test the program. Use hashmap for the update method. You can also use it for the getIndex method. public int getIndex(AnyType x) { //average case O(1) //returns the index of the item in the heap //or -1 if it isn't in the heap //return -1;
Must attach output screenshot, editable output
In java
Implement a generic min heap class and write a test code to test the program. Use hashmap for the update method. You can also use it for the getIndex method.
public int getIndex(AnyType x) {
//average case O(1)
//returns the index of the item in the heap
//or -1 if it isn't in the heap
//return -1;
}
public boolean update(AnyType x) {
//O(lg n) average case
//or O(lg n) worst case if getIndex() is guarenteed O(1)
We want an update() operation which increases (or decreases) the priority of the item. The item (or an equal item) will be provided and it should update the priority queue appropriately.
The only way to do this efficiently is to use a map to map heap items to indexes so that you know where to start the update (in average case O(1) time). Without this, update() would be O(n) and not O(lg n). Therefore before you implement updating, you need to integrate a map into the code. Whenever an item is placed, moved, or removed from the heap, the map should updated to reflect the item's new index (or remove it from the map in the case of removal from the heap).
return false; //dummy return
Trending now
This is a popular solution!
Step by step
Solved in 2 steps
