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.
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
4
- 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.
answered Jun 16, 2020 at 6:14
-
$\begingroup$ @idmean in the question he stated he has an auxiliary map that maps keys to their index. If this map is a haap then yea, worst case is $O(n)$, but average case is $O(1)$. If it is implemented with some other data structure, like a BST then you can find it in $O(\log(n))$ $\endgroup$ Commented Jul 11, 2021 at 14:28
-
$\begingroup$ Sorry, I missed that. Weird setup. If the map is a search tree, this actually makes the heap itself kind of redundant... $\endgroup$– idmeanCommented Jul 11, 2021 at 14:33
-
$\begingroup$ @idemean I get you. The same thing crossed my mind at first, until i noticed it. Also, i agree that in some sense it is redundant... $\endgroup$ Commented Jul 11, 2021 at 15:08
-
$\begingroup$ @idemean I get you. The same thing crossed my mind at first, until i noticed it. Also, i agree that in some sense it is redundant... $\endgroup$ Commented Jul 11, 2021 at 15:09