Home » Heap » Min Heap and Max Heap in Java

Min Heap and Max Heap in Java

in - on 09:29:00 - No comments

Min Heap and Max Heap in Java.

In this post we will see what is Min Heap, Max Heap, the operation it supports and the time and space complexity of each operation.

Complete Binary Tree.
Min Heap and Max Heap uses the concept of Complete Binary Tree.

A heap (Binary heap here) is a complete binary tree which satisfies below property,

Min-heap: the value of each node is greater than or equal to the value of its parent, that is the element with minimum value is always at the root. 
Max-heap: the value of each node is less than or equal to the value of its parent, that is the element with maximum value is always at the root.

If we represent the array as Complete Binary tree, how is left child and right child index calculated?
Check this link which explains heap concepts in detail Heap Sort Algorithm

In this post, we will implement Min Heap and the operation it support would be,
  • add - this will add a element to a heap
  • remove - this will remove a element from a heap
  • peek - this will give you a minimum element in a heap
Time complexity of each operation,
  • add - O(log n)
  • remove - O(log n)
  • peek - O(1)
Since in addition/removal, new element added/removed could disturb the heap property so we have to scan all the elements belonging to height of binary tree which take Log n operation.

Min Heap in Java

 
package javabypatel.heap;

public class MinHeap {
    private int[] heap;
    private int size;
    private int currentIndex=-1;

    public MinHeap(int size) {
        this.heap = new int[size];
        this.size = size;
    }

    public int remove() {
        if (currentIndex < 0) {
            throw new RuntimeException("Heap is empty");
        }
        int temp = heap[0];
        heap[0] = heap[currentIndex];
        currentIndex--;
        bubbleDown(0);
        return temp;
    }

    public int peek() {
        if (currentIndex < 0) {
            throw new RuntimeException("Heap is empty");
        }
        return heap[0];
    }

    public void add(int data) {
        if ((currentIndex + 1) >= size) {
            throw new RuntimeException("Heap full");
        }

        heap[++currentIndex] = data;
        bubbleUp(currentIndex);
    }

    private int getLeftChildIndex(int index) {
        return index * 2 + 1;
    }

    private int getRightChildIndex(int index) {
        return index * 2 + 2;
    }

    private int getParentIndex(int index) {
        return (index - 1) / 2;
    }

    private boolean isParentPresent(int index) {
        return getParentIndex(index) >= 0;
    }

    private void bubbleUp(int index) {
        if (!isParentPresent(index)) {
            return;
        }

        int parentIndex = getParentIndex(index);

        if (heap[index] < heap[parentIndex]) {
            swap(index, parentIndex);
            bubbleUp(parentIndex);
        }
    }

    private void bubbleDown(int index) {
        int left = getLeftChildIndex(index);
        int right = getRightChildIndex(index);

        int minIndex = index;
        if (left <= currentIndex && heap[left] < heap[minIndex]) {
            minIndex = left;
        }
        if (right <= currentIndex && heap[right] < heap[minIndex]) {
            minIndex = right;
        }

        if (index != minIndex) {
            swap(index, minIndex);
            bubbleDown(minIndex);
        }
    }

    private void swap(int index1, int index2) {
        int temp = heap[index1];
        heap[index1] = heap[index2];
        heap[index2] = temp;
    }
}


 
package javabypatel.heap;

public class MinHeapMain {
    public static void main(String[] args) {
        MinHeap minHeap = new MinHeap(10);
        minHeap.add(5);
        minHeap.add(1);
        System.out.println(minHeap.peek());
        minHeap.remove();
        minHeap.add(4);
        System.out.println(minHeap.peek());
        minHeap.add(2);
        System.out.println(minHeap.peek());
    }
}
Output: 
1 
4 
2 

Max Heap is very similar to Min Heap, except we keep the maximum at the top.

Max Heap in Java
package javabypatel.heap;

public class MaxHeap {
    private int[] heap;
    private int size;
    private int currentIndex=-1;

    public MaxHeap(int size) {
        this.heap = new int[size];
        this.size = size;
    }

    public int remove() {
        if (currentIndex < 0) {
            throw new RuntimeException("Heap is empty");
        }
        int temp = heap[0];
        heap[0] = heap[currentIndex];
        currentIndex--;
        bubbleDown(0);
        return temp;
    }

    public int peek() {
        if (currentIndex < 0) {
            throw new RuntimeException("Heap is empty");
        }
        return heap[0];
    }

    public void add(int data) {
        if ((currentIndex + 1) >= size) {
            throw new RuntimeException("Heap full");
        }

        heap[++currentIndex] = data;
        bubbleUp(currentIndex);
    }

    private int getLeftChildIndex(int index) {
        return index * 2 + 1;
    }

    private int getRightChildIndex(int index) {
        return index * 2 + 2;
    }

    private int getParentIndex(int index) {
        return (index - 1) / 2;
    }

    private boolean isParentPresent(int index) {
        return getParentIndex(index) >= 0;
    }

    private void bubbleUp(int index) {
        if (!isParentPresent(index)) {
            return;
        }

        int parentIndex = getParentIndex(index);

        if (heap[index] > heap[parentIndex]) {
            swap(index, parentIndex);
            bubbleUp(parentIndex);
        }
    }

    private void bubbleDown(int index) {
        int left = getLeftChildIndex(index);
        int right = getRightChildIndex(index);

        int minIndex = index;
        if (left <= currentIndex && heap[left] > heap[minIndex]) {
            minIndex = left;
        }
        if (right <= currentIndex && heap[right] > heap[minIndex]) {
            minIndex = right;
        }

        if (index != minIndex) {
            swap(index, minIndex);
            bubbleDown(minIndex);
        }
    }

    private void swap(int index1, int index2) {
        int temp = heap[index1];
        heap[index1] = heap[index2];
        heap[index2] = temp;
    }

}

package javabypatel.heap;

public class MaxHeapMain {
    public static void main(String[] args) {
        MaxHeap maxHeap = new MaxHeap(10);
        maxHeap.add(5);
        maxHeap.add(1);
        System.out.println(maxHeap.peek());
        maxHeap.remove();
        System.out.println(maxHeap.peek());
        maxHeap.add(15);
        System.out.println(maxHeap.peek());
        maxHeap.add(20);
        System.out.println(maxHeap.peek());
    }
}
Output: 
5 
1 
15 
20

Categories:

Post a Comment