Binary Min-Max Heap Implementation

by

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

Related Posts: