What is the best way to implement a Min-Max Heap in Java, and how can I efficiently access both the minimum and maximum elements?

General Discussions
1

Do you know of any popular libraries (Apache, Google, etc.) that provide a reliable Java implementation for a max heap Java*structure that allows peeking at both the minimum and maximum values in O(1) and removing elements in O(log n)?

2

If you’re looking for a Min-Max Heap in Java, you’re essentially asking for a data structure that allows quick access to both the minimum and maximum elements in O(1) while maintaining efficient insertions and deletions in O(log n).

Unfortunately, the standard Java collections framework does not provide a built-in Min-Max Heap,

One of the most straightforward approaches—you maintain two heaps:

A Min-Heap (PriorityQueue in Java) to track the smallest element. A Max-Heap (PriorityQueue with a custom comparator) to track the largest element.

Why?

You get O(1) access to both the minimum and maximum values. Insertions and deletions are O(log n). This is easy to implement using Java’s PriorityQueue.

Code Example:

import java.util.Collections; import java.util.PriorityQueue;

class MinMaxHeap { private PriorityQueue minHeap = new PriorityQueue<>(); // Default Min-Heap private PriorityQueue maxHeap = new PriorityQueue<>(Collections.reverseOrder()); // Max-Heap

public void insert(int num) {
    minHeap.offer(num);
    maxHeap.offer(num);
}

public int getMin() {
    return minHeap.peek();  // O(1) access to min
}

public int getMax() {
    return maxHeap.peek();  // O(1) access to max
}

public boolean remove(int num) {
    return minHeap.remove(num) && maxHeap.remove(num); // O(log n)
}

public static void main(String[] args) {
    MinMaxHeap heap = new MinMaxHeap();
    heap.insert(10);
    heap.insert(20);
    heap.insert(5);
    System.out.println("Min: " + heap.getMin()); // 5
    System.out.println("Max: " + heap.getMax()); // 20
}

} :small_blue_diamond: Downside?

Slightly more memory usage since you maintain two heaps.

3

If you prefer a ready-made solution, Google’s Guava library provides a MinMaxPriorityQueue, which is specifically designed to retrieve both min and max efficiently!

Code Example:

import com.google.common.collect.MinMaxPriorityQueue;

class GuavaMinMaxHeap {
    public static void main(String[] args) {
        MinMaxPriorityQueue<Integer> minMaxHeap = MinMaxPriorityQueue.create();
        
        minMaxHeap.add(10);
        minMaxHeap.add(20);
        minMaxHeap.add(5);

        System.out.println("Min: " + minMaxHeap.peekFirst()); // 5
        System.out.println("Max: " + minMaxHeap.peekLast());  // 20
    }
}

🔹 Downside? Requires adding the Guava library dependency:

<dependency>
    <groupId>com.google.guava</groupId>
    <artifactId>guava</artifactId>
    <version>31.0.1-jre</version>
</dependency>
4

If you’re building a performance-critical application, you might want to implement a Min-Max Heap from scratch.

Basic Idea:

Use a single array-based binary heap with even levels acting as a min heap and odd levels acting as a max heap.

Parent-child relationships are adjusted accordingly.

Here’s a simplified starting point for a Min-Max Heap implementation:

class MinMaxHeap {
    private int[] heap;
    private int size;

    public MinMaxHeap(int capacity) {
        heap = new int[capacity];
        size = 0;
    }

    public void insert(int value) {
        heap[size++] = value;
        heapifyUp(size - 1);
    }

    private void heapifyUp(int index) {
        int parent = (index - 1) / 2;
        if (index > 0 && heap[index] < heap[parent]) {
            swap(index, parent);
            heapifyUp(parent);
        }
    }

    public int getMin() {
        return size > 0 ? heap[0] : -1;
    }

    public int getMax() {
        return size > 1 ? Math.max(heap[1], heap[2]) : heap[0];
    }

    private void swap(int i, int j) {
        int temp = heap[i];
        heap[i] = heap[j];
        heap[j] = temp;
    }

    public static void main(String[] args) {
        MinMaxHeap heap = new MinMaxHeap(10);
        heap.insert(10);
        heap.insert(5);
        heap.insert(20);

        System.out.println("Min: " + heap.getMin()); // 5
        System.out.println("Max: " + heap.getMax()); // 20
    }
}