Binary Min-Max Heap Implementation

A binary heap is a heap data structure created using a binary tree.

binary tree has two rules –

  1. Binary Heap has to be a complete binary tree at all levels except the last level. This is called a shape property.
  2. All nodes are either greater than equal to (Max-Heap) or less than equal to (Min-Heap) to each of its child nodes. This is called heap property.

Implementation:

  • Use an array to store the data.
  • Start storing from index 1, not 0.
  • For any given node at position i:
  • Its Left Child is at [2*i] if available.
  • Its Right Child is at [2*i+1] if available.
  • Its Parent Node is at [i/2]if available.
Max-Heap
Max-Heap
Min-Heap
Min-Heap

Heap Majorly has 3 operations –

  1. Insert Operation
  2. Delete Operation
  3. Extract-Min (OR Extract-Max)

Insert Operation:

  • Add the element at the bottom leaf of the Heap.
  • Perform the Bubble-Up operation.
  • All Insert Operations must perform the bubble-up operation(it is also called as up-heap, percolate-up, sift-up, trickle-up, heapify-up, or cascade-up)
Insert() - Bubble-Up Min-Heap
Insert() – Bubble-Up Min-Heap

Extract-Min OR Extract-Max Operation:

  • Take out the element from the root.( it will be minimum in case of Min-Heap and maximum in case of Max-Heap).
  • Take out the last element from the last level from the heap and replace the root with the element.
  • Perform Sink-Down
  • All delete operations must perform Sink-Down Operation ( also known as bubble-down, percolate-down, sift-down, trickle-down, heapify-down, cascade-down).

Sink-Down Operation:

  • If the replaced element is greater than any of its child node in case of Min-Heap OR smaller than any if its child node in case of Max-Heap, swap the element with its smallest child(Min-Heap) or with its greatest child(Max-Heap).
  • Keep repeating the above step, if the node reaches its correct position, STOP.
Delete OR Extract Min from Heap
Delete OR Extract Min from Heap

Delete Operation:

  • Find the index for the element to be deleted.
  • Take out the last element from the last level from the heap and replace the index with this element .
  • Perform Sink-Down

Time and Space Complexity:

SpaceO(n)
SearchO(n)
InsertO(log n)
DeleteO(log n)

Complete Code for Min-Heap:

Java

public class minHeap {
    public int capacity;
    public int [] mH;
    public int currentSize;
    public minHeap(int capacity){
        this.capacity=capacity;
        mH = new int [capacity+1];
       currentSize =0;
    }
    public void createHeap(int [] arrA){
        if(arrA.length>0){
            for(int i=0;i<arrA.length;i++){
                insert(arrA[i]);
            }
        }
    }
    public void display(){
        for(int i=1;i<mH.length;i++){
            System.out.print(" " + mH[i]);
        }
        System.out.println("");
    }
    public void insert(int x) {
        if(currentSize==capacity){
            System.out.println("heap is full");
            return;
        }
        currentSize++;
        int idx = currentSize;
        mH[idx] = x;
        bubbleUp(idx);
    }

    public void bubbleUp(int pos) {
        int parentIdx = pos/2;
        int currentIdx = pos;
        while (currentIdx > 0 && mH[parentIdx] > mH[currentIdx]) {

            swap(currentIdx,parentIdx);
            currentIdx = parentIdx;
            parentIdx = parentIdx/2;
        }
    }

    public int extractMin() {
        int min = mH[1];
        mH[1] = mH[currentSize];
        mH[currentSize] = 0;
        sinkDown(1);
        currentSize--;
        return min;
    }

    public void sinkDown(int k) {
        int smallest = k;
        int leftChildIdx = 2 * k;
        int rightChildIdx = 2 * k+1;
        if (leftChildIdx < heapSize() && mH[smallest] > mH[leftChildIdx]) {
            smallest = leftChildIdx;
        }
        if (rightChildIdx < heapSize() && mH[smallest] > mH[rightChildIdx]) {
            smallest = rightChildIdx;
        }
        if (smallest != k) {

            swap(k, smallest);
            sinkDown(smallest);
        }
    }

    public void swap(int a, int b) {
        int temp = mH[a];
        mH[a] = mH[b];
        mH[b] = temp;
    }
    public boolean isEmpty() {
        return currentSize == 0;
    }

    public int heapSize(){
        return currentSize;
    }

    public static void main(String args[]){
        int arrA [] = {3,2,1,7,8,4,10,16,12};
        System.out.print("Original Array : ");
        for(int i=0;i<arrA.length;i++){
            System.out.print("  " + arrA[i]);
        }
        minHeap m = new minHeap(arrA.length);
        System.out.print("\nMin-Heap : ");
        m.createHeap(arrA);
        m.display();
        System.out.print("Extract Min :");
        for(int i=0;i<arrA.length;i++){
            System.out.print("  " + m.extractMin());
        }
    }
}

Output:

Original Array : 3 2 1 7 8 4 10 16 12 
Min-Heap : 1 3 2 7 8 4 10 16 12 
Sorted: 1 3 2 12 8 4 10 16 0

5 thoughts on “Binary Min-Max Heap Implementation”

  1. there is a mistake in this code i guess. u are maintaining the variable position as public . but the bubble up takes the same public value of the variable and alters it which will effect our data structure when we try to insert an element into the min or max heap .

    Reply

Leave a Comment

This site uses Akismet to reduce spam. Learn how your comment data is processed.