fork download
copy 
  1. /* package whatever; // don't place package name! */
  2.  
  3. import java.util.*;
  4. import java.lang.*;
  5. import java.io.*;
  6.  
  7. /* Name of the class has to be "Main" only if the class is public. */
  8. class MinHeap { 
  9.     private int[] Heap; 
  10.     private int size; 
  11.     private int maxsize; 
  12.  
  13.     private static final int FRONT = 1; 
  14.  
  15.     public MinHeap(int maxsize) 
  16.     { 
  17.         this.maxsize = maxsize; 
  18.         this.size = 0; 
  19.         Heap = new int[this.maxsize + 1]; 
  20.         Heap[0] = Integer.MIN_VALUE; 
  21.     } 
  22.  
  23.     // Function to return the position of 
  24.     // the parent for the node currently 
  25.     // at pos 
  26.     private int parent(int pos) 
  27.     { 
  28.         return pos / 2; 
  29.     } 
  30.  
  31.     // Function to return the position of the 
  32.     // left child for the node currently at pos 
  33.     private int leftChild(int pos) 
  34.     { 
  35.         return (2 * pos); 
  36.     } 
  37.  
  38.     // Function to return the position of 
  39.     // the right child for the node currently 
  40.     // at pos 
  41.     private int rightChild(int pos) 
  42.     { 
  43.         return (2 * pos) + 1; 
  44.     } 
  45.  
  46.     // Function that returns true if the passed 
  47.     // node is a leaf node 
  48.     private boolean isLeaf(int pos) 
  49.     { 
  50.         if (pos >= (size / 2) && pos <= size) { 
  51.             return true; 
  52.         } 
  53.         return false; 
  54.     } 
  55.  
  56.     // Function to swap two nodes of the heap 
  57.     private void swap(int fpos, int spos) 
  58.     { 
  59.         int tmp; 
  60.         tmp = Heap[fpos]; 
  61.         Heap[fpos] = Heap[spos]; 
  62.         Heap[spos] = tmp; 
  63.     } 
  64.  
  65.     // Function to heapify the node at pos 
  66.     private void minHeapify(int pos) 
  67.     { 
  68.  
  69.         // If the node is a non-leaf node and greater 
  70.         // than any of its child 
  71.         if (!isLeaf(pos)) { 
  72.             if (Heap[pos] > Heap[leftChild(pos)] 
  73.                 || Heap[pos] > Heap[rightChild(pos)]) { 
  74.  
  75.                 // Swap with the left child and heapify 
  76.                 // the left child 
  77.                 if (Heap[leftChild(pos)] < Heap[rightChild(pos)]) { 
  78.                     swap(pos, leftChild(pos)); 
  79.                     minHeapify(leftChild(pos)); 
  80.                 } 
  81.  
  82.                 // Swap with the right child and heapify 
  83.                 // the right child 
  84.                 else { 
  85.                     swap(pos, rightChild(pos)); 
  86.                     minHeapify(rightChild(pos)); 
  87.                 } 
  88.             } 
  89.         } 
  90.     } 
  91.  
  92.     // Function to insert a node into the heap 
  93.     public void insert(int element) 
  94.     { 
  95.         if (size >= maxsize) { 
  96.             return; 
  97.         } 
  98.         Heap[++size] = element; 
  99.         int current = size; 
  100.  
  101.         while (Heap[current] < Heap[parent(current)]) { 
  102.             swap(current, parent(current)); 
  103.             current = parent(current); 
  104.         } 
  105.     } 
  106.  
  107.     // Function to print the contents of the heap 
  108.     public void print() 
  109.     { 
  110.         for (int i = 1; i <= size / 2; i++) { 
  111.             System.out.print(Heap[i] + " ");
  112.             System.out.println(); 
  113.         } 
  114.     } 
  115.  
  116.     // Function to build the min heap using 
  117.     // the minHeapify 
  118.     public void minHeap() 
  119.     { 
  120.         for (int pos = (size / 2); pos >= 1; pos--) { 
  121.             minHeapify(pos); 
  122.         } 
  123.     } 
  124.  
  125.     // Function to remove and return the minimum 
  126.     // element from the heap 
  127.     public int remove() 
  128.     { 
  129.         int popped = Heap[FRONT]; 
  130.         Heap[FRONT] = Heap[size--]; 
  131.         minHeapify(FRONT); 
  132.         return popped; 
  133.     } 
  134. }
  135. class Ideone
  136. {
  137. 	public static void main (String[] args) throws java.lang.Exception
  138. 	{
  139. 		// your code goes here
  140. 		System.out.println("The Min Heap is "); 
  141.         MinHeap minHeap = new MinHeap(15); 
  142.         minHeap.insert(5); 
  143.         minHeap.insert(3); 
  144.         minHeap.insert(17); 
  145.         minHeap.insert(10); 
  146.         minHeap.insert(84); 
  147.         minHeap.insert(19); 
  148.         minHeap.insert(6); 
  149.         minHeap.insert(22); 
  150.         minHeap.insert(9); 
  151.         minHeap.minHeap(); 
  152.  
  153.         minHeap.print(); 
  154.         System.out.println("The Min val is " + minHeap.remove());
  155.         minHeap.print();
  156. 	}
  157. }
Success #stdin #stdout 0.15s 57516KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
The Min Heap is 
3 
5 
6 
9 
The Min val is 3
5 
9 
6 
10
https://ideone.com/luzVY0
language:
Java (HotSpot 12)
created:
4 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!