CODEWITHSUNDEEP
javadata-structuresminmax-heap
Yuval Adam
Yuval Adam

Reputation: 165340

Java implementation for Min-Max Heap?

Do you know of a popular library (Apache, Google, etc, collections) which has a reliable Java implementation for a min-max heap, that is a heap which allows to peek its minimum and maximum value in O(1) and to remove an element in O(log n)?

Upvotes: 52

Views: 117234

Answers (7)

NamshubWriter
NamshubWriter

Reputation: 24326

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.

Upvotes: 4

Fahad Israr
Fahad Israr

Reputation: 1239

Well you can simply pass the comparator to be used to compare elements. This will become useful even when you want to sort objects based on some attributes. Look at the following examples:

  • Min Heap :

    PriorityQueue<Integer> pq = new PriorityQueue<>((a,b) -> a - b);

  • Max Heap :

    PriorityQueue<Integer> pq = new PriorityQueue<>((a,b) -> b - a);

  • Min Heap for Objects

    PriorityQueue<MyObject> pq = new PriorityQueue<>((obj1, obj2) -> obj1.getId() - obj2.getId());

  • Max Heap for Objects

    PriorityQueue<MyObject> pq = new PriorityQueue<>((obj1, obj2) -> obj2.getId() - obj1.getId());

Upvotes: 12

Mohammad
Mohammad

Reputation: 6148

Java has good tools in order to implement min and max heaps. My suggestion is using the priority queue data structure in order to implement these heaps. For implementing the max heap with priority queue try this:

import java.util.PriorityQueue;

public class MaxHeapWithPriorityQueue {

    public static void main(String args[]) {
    // create priority queue
    PriorityQueue<Integer> prq = new PriorityQueue<>(Collections.reverseOrder());

    // insert values in the queue
    prq.add(6);
    prq.add(9);
    prq.add(5);
    prq.add(64);
    prq.add(6);

    //print values
    while (!prq.isEmpty()) {
        System.out.print(prq.poll()+" ");
    }
    }

}

For implementing the min heap with priority queue, try this:

import java.util.PriorityQueue;

public class MinHeapWithPriorityQueue {

    public static void main(String args[]) {
        // create priority queue
        PriorityQueue< Integer > prq = new PriorityQueue <> ();

        // insert values in the queue
        prq.add(6);
        prq.add(9);
        prq.add(5);
        prq.add(64);
        prq.add(6);

        //print values
        while (!prq.isEmpty()) {
            System.out.print(prq.poll()+" ");
        }
    }

}

For more information, please visit:

Upvotes: 39

Vip
Vip

Reputation: 1616

Min Heap: PriorityQueue minHeap= new PriorityQueue<>();

Max Heap PriorityQueue maxHeap= new PriorityQueue<>(Comparator.reverseOrder());

Upvotes: 13

Louis Wasserman
Louis Wasserman

Reputation: 198471

From Guava: MinMaxPriorityQueue.

Upvotes: 44

Il-Bhima
Il-Bhima

Reputation: 10880

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.

Upvotes: 28

Nat
Nat

Reputation: 9951

The java.util.TreeSet class.

Upvotes: 0

Related Questions