[Solved]: Heap-like data structure allowing peek at largest & smallest

Problem Detail: 

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 Increase-key and decrease-key in a binary min-heap

Asked By : Snowbody

Answered By : D.W.

One simple approach is to use a max-heap. Separately keep track of the minimum element stored in the heap. Then all operations can be done relatively efficiently:

• Load from array can be done in $O(n)$ time, building Build-Heap.

• Each of the peek operations takes $O(1)$ time.

• Decreasing the maximum element can be done in $O(\lg n)$ time. You decrease it and fix up the heap property (or extract it and re-insert it). Then, check whether it got reduced below the previous-smallest and if so update the minimum.

This seems likely to be reasonable for many workloads.

---

Alternatively, you could store the elements as a balanced binary tree with the leaves in sorted order. Keep track of a pointer to the leftmost leaf and a pointer to the rightmost heap.

• To load from array, sort the elements and then create a balanced binary tree; this can be done in $O(n \lg n)$ time.

• All of the peek operations take $O(1)$ time.

• The decrease operation can be implemented in $O(\lg n)$ time, by deleting the maximum and then inserting it in the new place, using standard data structures for balanced binary trees that support $O(\lg n)$ time insertion and deletion (e.g., AVL trees, red-black trees, etc.)

This too will likely be reasonable for many workloads.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/42048

 Ask a Question

 Download Related Notes/Documents