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
1
For the max stuff I’d use a heap, for the min a simple variable (to be potentially updated when the decrease operation lets the previous maximum fall all the way to the bottom of the heap).
2
I don’t remember i ever encountered a real life situation when a heap was the best solution.
It sounds to me that what you need is a self balancing Self-balancing binary search tree
. You should probably look into AVL trees, and Red-Black Trees.
Binary Search Trees have very similar performance characteristics to a Heap, but they are much more useful, and can help you solve a lot of problems quite trivially.
P.S.
Here is a useful way to find the K’th smallest element in a search tree.
6