5

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

Improve this question
1

2 Answers 2

Reset to default
6

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).

Improve this answer
2
  • This is best of both worlds. By adding one extra comparison, you can keep your heap pure and meet all the requirements.
    – BobDalgleish
    Commented May 2, 2015 at 11:39
  • That's a nice and simple solution...
    – AK_
    Commented May 2, 2015 at 12:18
0

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.

Improve this answer
6
  • 1
    Really? Never used priority queue in real life?
    – Honza Brabec
    Commented May 2, 2015 at 12:05
  • @HonzaBrabec Obviously sometimes a Heap is the best solution. But I can't recall ever requiring a "Priority Queue", when I didn't need to be able to search the data, nor hold it in sorted form (for presentation and the sort)...
    – AK_
    Commented May 2, 2015 at 12:31
  • 1
    Looks like you forgot a link in your P.S.
    – Stefan Pochmann
    Commented May 2, 2015 at 14:36
  • Could you explain what benefit the balanced binary tree has? Simpler code, runtime? I don't need it to be more useful in general, just able to support the operations I have listed. Seems to me that a plain ol binary heap has better performance.
    – Snowbody
    Commented May 4, 2015 at 13:06
  • To compare performance we need specific data structures to compare. There are several kinds of search trees and heeps. I like BSTs for two reasons: 1. There are lots of good ready libraries and ready implementations. 2. BSTs give an ordered structure and allow you to do many manipulations on them at ~O(logn)
    – AK_
    Commented May 4, 2015 at 17:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.