Java implementation for Min-Max Heap?

views:

1444

answers:

+4 Q:

Java implementation for Min-Max Heap?

Do you know of a popular library (apache collections, google collections, etc...) which has a reliable Java implementation for a Min-Max heap?

I.e. a heap which allows to peek at its minimum and maximum value in O(1) and to remove at O(logn).

I did a quick search and couldn't find one. Anyone know better?

The java.util.TreeSet class.

Nat 2009-07-08 14:03:40

I need support for duplicate values... Set is "a bit" problematic in this aspect.

Yuval A 2009-07-08 14:10:00

-1 TreeSet implements most operations in O(log n) - the requirement was for peeking at the minimum and maximum in O(1).

Avi 2009-07-08 14:12:44

TreeSet also doesn't have a decreaseKey or increaseKey operation, which is one of the definitive operations of a heap. See http://en.wikipedia.org/wiki/Heap_(data_structure)

NamshubWriter 2009-07-08 14:14:12

If you need to support duplicate values, you can use TreeBag (http://commons.apache.org/collections/api-release/org/apache/commons/collections/bag/TreeBag.html) from Apache Commons Collections, or TreeMultiset (http://google-collections.googlecode.com/svn/trunk/javadoc/com/google/common/collect/TreeMultiset.html) from Google Collections. If you need to increaseKey or decreaseKey, you can simply remove the element and re-add it.

newacct 2009-07-08 18:35:33

Or use a TreeMap that maps keys to counts. TreeSet is actually implemented with a TreeMap under the hood.

Nat 2009-07-08 18:38:10

-1. TreeSet/TreeMap is a red-black tree, not a heap.

dty 2010-09-16 12:30:11

+2 A:

How about com.aliasi.util.MinMaxHeap? This is part of LingPipe; unfortunately, the licensing may be a problem.

See this related paper.

Doesn't implement decreaseKey or increaseKey, though.

NamshubWriter 2009-07-08 14:25:44

+1 A:

Instead of a max-min heap, could you use two instances of a java.util.PriorityQueue containing the same elements? The first instance would be passed a comparator which puts the maximum at the head, and the second instance would use a comparator which puts the minimum at the head.

The downside is that add, delete, etc would have to be performed on both structures, but it should satisfy your requirements.

Il-Bhima 2009-07-08 14:26:17

+1. This is a good answer given the stated requirements to peek the root in O(1) and remove it in O(log.n). Note however, that a PriorityQueue doesn't implement all heap operations (e.g. decreaseKey, increaseKey).

dty 2010-09-16 12:36:07

ansaurus

tags:

views:

answers:

Java implementation for Min-Max Heap?

related questions