How would you write a method to change the value of a min heap where bool changeKey(int oldKey, int newKey). The keys are unique, no duplicate keys are permitted. If there is a key in the heap with value oldKey, and no existing entry with key newKey, it will change it to newKey, keeping the the heap properties and returning true. If there is no key in the heap with value oldKey, or an existing entry has value newKey, then it will take no action and return false. Also an auxiliary map is used to store the locations of the keys in an array. I know how to write methods for insertion but haven't seen any implementations of this.
- Find the key's node
- Change the node's key to the new key
- Heapify the node
- Update the mapping in the auxiliary map
This will work in $O(log(n))$ worst case.
If the old key is the new key the node wont move. You can also explicitly check it before searching for the node, if you prefer.