Timeline for Method to change value in a key for a min heap
Current License: CC BY-SA 4.0
6 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 11, 2021 at 15:09 | comment | added | nir shahar | @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... | |
| Jul 11, 2021 at 15:08 | comment | added | nir shahar | @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... | |
| Jul 11, 2021 at 14:33 | comment | added | idmean | Sorry, I missed that. Weird setup. If the map is a search tree, this actually makes the heap itself kind of redundant... | |
| Jul 11, 2021 at 14:29 | history | edited | nir shahar | CC BY-SA 4.0 |
added 43 characters in body
|
| Jul 11, 2021 at 14:28 | comment | added | nir shahar | @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))$ | |
| Jun 16, 2020 at 6:14 | history | answered | nir shahar | CC BY-SA 4.0 |