Problem: Min-Heap
When we think of a min-heap {same as max-heap just look for smallest instead of biggest}, we usually think of inserting a value that stays the same while it's in the heap. It onlyr exits the heap once it's the smallest value. However, there are cases when it's helpful to allow a value in the heap to change. When it changes: the effect on the min-heap is calculated. For example: if we have a min-heap with [10,50. 100 ] and | change the value of 100 to 1, then the new min- heap could be[1l50, 1O ].
Design an object, in pseudocode or C++ if you like, that implements a min-heap that supports modi?cation of items. Here are the requirements:
1) Each entry in the min-heap is two parts: a key (assume an int) and a priority. The key is used to look up items in the min-heap: and the prion'ty is used to order the min-heap.
2) The object must allow for entries in the heap to be looked-up and modified in O(log n) time. However: the entry is only allowed to get smaller: not larger. You may abort or ignore a request to make the entry larger.
3) After modification, the min-heap must be returned to a valid min-heap status in O(log n) time.
4) The min-heap must be implemented as an array.
Make sure your answer shows the design of the object and explains how it achieves all of the requirements.