For the purpose of implementing an optimization algorithm (finding the minimum of a multivariate function) I want to create a data structure that supports the following operations:
- load from array
- Peek at maximum element (but don't destroy it)
- Peek at next-to-maximum element
- Peek at minimum element
- decrease the maximum element
Once initialized, the data structure always stores the same number of elements.
Currently I'm just using an unsorted array, and searching the array each time to find the max, next-to-max, and min elements, and updating the max element when necessary.
I considered using a heap / priority queue, but those don't seem ideal, as they support adding and removing elements, which I don't need to do. They also don't natively support "decrease the maximum element", just "increase an arbitrary element" so I'd have to extract-max and then re-add it.
I also considered a sorted array in a ring buffer, which seems like it would be better than just a sorted array, as I'd only have to move at most half of the list.
Wikipedia talks about some complicated data structures (Fibonacci heaps) that I vaguely remember from my sophomore algorithms class in college, but those seem like overkill (and they also support features I don't need and don't support features I need).
Well, now I search again and I find my question is sort of kind of a duplicate of https://cs.stackexchange.com/questions/10203/increase-key-and-decrease-key-in-a-binary-min-heap