Java Program to Implement Min Heap

This Java program is to implement Min heap. A Heap data structure is a Tree based data structure that satisfies the HEAP Property “If A is a parent node of B then key(A) is ordered with respect to key(B) with the same ordering applying across the heap.”
So in a Min Heap this property will be “If A is a parent node of B then key(A) is less than key(B) with the same ordering applying across the heap.” and in a max heap the key(A) will be greater than Key(B).

Here is the source code of the Java program to implement Min heap. The Java program is successfully compiled and run on a Linux system. The program output is also shown below.

public class MinHeap
{
    private int[] Heap;
    private int size;
    private int maxsize;
 
    private static final int FRONT = 1;
 
    public MinHeap(int maxsize)
    {
        this.maxsize = maxsize;
        this.size = 0;
        Heap = new int[this.maxsize + 1];
        Heap[0] = Integer.MIN_VALUE;
    }
 
    private int parent(int pos)
    {
        return pos / 2;
    }
 
    private int leftChild(int pos)
    {
        return (2 * pos);
    }
 
    private int rightChild(int pos)
    {
        return (2 * pos) + 1;
    }
 
    private boolean isLeaf(int pos)
    {
        if (pos >=  (size / 2)  &&  pos <= size)
        { 
            return true;
        }
        return false;
    }
 
    private void swap(int fpos, int spos)
    {
        int tmp;
        tmp = Heap[fpos];
        Heap[fpos] = Heap[spos];
        Heap[spos] = tmp;
    }
 
    private void minHeapify(int pos)
    {
        if (!isLeaf(pos))
        { 
            if ( Heap[pos] > Heap[leftChild(pos)]  || Heap[pos] > Heap[rightChild(pos)])
            {
                if (Heap[leftChild(pos)] < Heap[rightChild(pos)])
                {
                    swap(pos, leftChild(pos));
                    minHeapify(leftChild(pos));
                }else
                {
                    swap(pos, rightChild(pos));
                    minHeapify(rightChild(pos));
                }
            }
        }
    }
 
    public void insert(int element)
    {
        Heap[++size] = element;
        int current = size;
 
        while (Heap[current] < Heap[parent(current)])
        {
            swap(current,parent(current));
            current = parent(current);
        }	
    }
 
    public void print()
    {
        for (int i = 1; i <= size / 2; i++ )
        {
            System.out.print(" PARENT : " + Heap[i] + " LEFT CHILD : " + Heap[2*i] 
                + " RIGHT CHILD :" + Heap[2 * i  + 1]);
            System.out.println();
        } 
    }
 
    public void minHeap()
    {
        for (int pos = (size / 2); pos >= 1 ; pos--)
        {
            minHeapify(pos);
        }
    }
 
    public int remove()
    {
        int popped = Heap[FRONT];
        Heap[FRONT] = Heap[size--]; 
        minHeapify(FRONT);
        return popped;
    }
 
    public static void main(String...arg)
    {
        System.out.println("The Min Heap is ");
        MinHeap minHeap = new MinHeap(15);
        minHeap.insert(5);
        minHeap.insert(3);
        minHeap.insert(17);
        minHeap.insert(10);
        minHeap.insert(84);
        minHeap.insert(19);
        minHeap.insert(6);
        minHeap.insert(22);
        minHeap.insert(9);
        minHeap.minHeap();
 
        minHeap.print();
        System.out.println("The Min val is " + minHeap.remove());
    }
}

$javac MinHeap.java
$java MinHeap
The Min Heap is 
 PARENT : 3 LEFT CHILD : 5 RIGHT CHILD :6
 PARENT : 5 LEFT CHILD : 9 RIGHT CHILD :84
 PARENT : 6 LEFT CHILD : 19 RIGHT CHILD :17
 PARENT : 9 LEFT CHILD : 22 RIGHT CHILD :10
The Min val is 3

Related posts:

Spring Security Remember Me
Hashtable trong java
RegEx for matching Date Pattern in Java
Java Program to Implement the Bin Packing Algorithm
An Intro to Spring Cloud Security
Java Program to Check Whether a Given Point is in a Given Polygon
Java Program to Implement Sorted Vector
Java Program to Implement Sorted Doubly Linked List
Các nguyên lý thiết kế hướng đối tượng – SOLID
Java Program to Create the Prufer Code for a Tree
Apache Tiles Integration with Spring MVC
Spring Boot - Tomcat Deployment
Spring 5 Functional Bean Registration
Java Program to Implement Knight’s Tour Problem
Java Program to Generate Random Numbers Using Probability Distribution Function
Java Program to Implement Karatsuba Multiplication Algorithm
Using Spring ResponseEntity to Manipulate the HTTP Response
Spring RequestMapping
Entity To DTO Conversion for a Spring REST API
Java Program to Implement the MD5 Algorithm
Java Program to Encode a Message Using Playfair Cipher
Difference Between Wait and Sleep in Java
How to Return 404 with Spring WebFlux
Java Program to Perform Postorder Non-Recursive Traversal of a Given Binary Tree
Hướng dẫn Java Design Pattern – Observer
Batch Processing with Spring Cloud Data Flow
Java Program to Implement Network Flow Problem
Guide to System.gc()
Notify User of Login From New Device or Location
Java Program to Check the Connectivity of Graph Using DFS
Tránh lỗi ConcurrentModificationException trong Java như thế nào?
Java Program to Implement Branch and Bound Method to Perform a Combinatorial Search