c - Data structure for the minimum value and its offset in a mutating array -

i have int array[4096]. want know minimum value , offset in array, without having ever search through it.

obviously, on setting element new value, can compared minimum , replace if applicable. however, if setting offset that's minimum, , making no longer minimum, gets more difficult.

how can done, efficiently possible?

you can use priority queue supporting deletion , decrease-key support this. whenever value changes, if value decreased, call decrease-key on decrease value in priority queue. if value increased, delete value , reinsert priority queue.

assuming priority queue backed structure efficiently supports these operations (typically, binary heaps appropriate bookkeeping can in o(log n) time each), can support faster doing linear scan on elements each time. if don't have binary heap lying around, can use tree-backed map (keys values, elements positions in array) this.

hope helps!