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.

  1. public class MinHeap
  2. {
  3.     private int[] Heap;
  4.     private int size;
  5.     private int maxsize;
  6.  
  7.     private static final int FRONT = 1;
  8.  
  9.     public MinHeap(int maxsize)
  10.     {
  11.         this.maxsize = maxsize;
  12.         this.size = 0;
  13.         Heap = new int[this.maxsize + 1];
  14.         Heap[0] = Integer.MIN_VALUE;
  15.     }
  16.  
  17.     private int parent(int pos)
  18.     {
  19.         return pos / 2;
  20.     }
  21.  
  22.     private int leftChild(int pos)
  23.     {
  24.         return (2 * pos);
  25.     }
  26.  
  27.     private int rightChild(int pos)
  28.     {
  29.         return (2 * pos) + 1;
  30.     }
  31.  
  32.     private boolean isLeaf(int pos)
  33.     {
  34.         if (pos >=  (size / 2)  &&  pos <= size)
  35.         { 
  36.             return true;
  37.         }
  38.         return false;
  39.     }
  40.  
  41.     private void swap(int fpos, int spos)
  42.     {
  43.         int tmp;
  44.         tmp = Heap[fpos];
  45.         Heap[fpos] = Heap[spos];
  46.         Heap[spos] = tmp;
  47.     }
  48.  
  49.     private void minHeapify(int pos)
  50.     {
  51.         if (!isLeaf(pos))
  52.         { 
  53.             if ( Heap[pos] > Heap[leftChild(pos)]  || Heap[pos] > Heap[rightChild(pos)])
  54.             {
  55.                 if (Heap[leftChild(pos)] < Heap[rightChild(pos)])
  56.                 {
  57.                     swap(pos, leftChild(pos));
  58.                     minHeapify(leftChild(pos));
  59.                 }else
  60.                 {
  61.                     swap(pos, rightChild(pos));
  62.                     minHeapify(rightChild(pos));
  63.                 }
  64.             }
  65.         }
  66.     }
  67.  
  68.     public void insert(int element)
  69.     {
  70.         Heap[++size] = element;
  71.         int current = size;
  72.  
  73.         while (Heap[current] < Heap[parent(current)])
  74.         {
  75.             swap(current,parent(current));
  76.             current = parent(current);
  77.         }	
  78.     }
  79.  
  80.     public void print()
  81.     {
  82.         for (int i = 1; i <= size / 2; i++ )
  83.         {
  84.             System.out.print(" PARENT : " + Heap[i] + " LEFT CHILD : " + Heap[2*i] 
  85.                 + " RIGHT CHILD :" + Heap[2 * i  + 1]);
  86.             System.out.println();
  87.         } 
  88.     }
  89.  
  90.     public void minHeap()
  91.     {
  92.         for (int pos = (size / 2); pos >= 1 ; pos--)
  93.         {
  94.             minHeapify(pos);
  95.         }
  96.     }
  97.  
  98.     public int remove()
  99.     {
  100.         int popped = Heap[FRONT];
  101.         Heap[FRONT] = Heap[size--]; 
  102.         minHeapify(FRONT);
  103.         return popped;
  104.     }
  105.  
  106.     public static void main(String...arg)
  107.     {
  108.         System.out.println("The Min Heap is ");
  109.         MinHeap minHeap = new MinHeap(15);
  110.         minHeap.insert(5);
  111.         minHeap.insert(3);
  112.         minHeap.insert(17);
  113.         minHeap.insert(10);
  114.         minHeap.insert(84);
  115.         minHeap.insert(19);
  116.         minHeap.insert(6);
  117.         minHeap.insert(22);
  118.         minHeap.insert(9);
  119.         minHeap.minHeap();
  120.  
  121.         minHeap.print();
  122.         System.out.println("The Min val is " + minHeap.remove());
  123.     }
  124. }


advertisement
$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

Sanfoundry Global Education & Learning Series – 1000 Java Programs.

Note: Join free Sanfoundry classes at Telegram or Youtube
advertisement
advertisement
If you wish to look at all Java Programming examples, go to Java Programs.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & technical discussions at Telegram SanfoundryClasses.