0
$\begingroup$

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.

$\endgroup$
1
$\begingroup$
  1. Find the key's node
  2. Change the node's key to the new key
  3. Heapify the node
  4. 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.

$\endgroup$
4
  • $\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$ – nir shahar Jul 11 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$ – idmean Jul 11 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$ – nir shahar Jul 11 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$ – nir shahar Jul 11 at 15:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.