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

Community
  • 1
Snowbody
  • 261
  • 1
  • 8
  • 1
    I asked kind of similar question few weeks ago and received really good answers: http://stackoverflow.com/questions/29674935/what-is-the-right-data-structure-for-a-queue-that-support-min-max-operations-in – bman May 02 '15 at 04:07

2 Answers2

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

Stefan Pochmann
  • 429
  • 3
  • 7
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.

Community
  • 1
AK_
  • 744
  • 3
  • 10
  • 1
    Really? Never used priority queue in real life? – Honza Brabec May 02 '15 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_ May 02 '15 at 12:31
  • 1
    Looks like you forgot a link in your P.S. – Stefan Pochmann May 02 '15 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 May 04 '15 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_ May 04 '15 at 17:16
  • Also you should look at binomial and Fibonacci heaps – AK_ May 04 '15 at 17:20