mjain

MIn heap

Jul 24th, 2019
31
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 2.79 KB | None | 0 0
  1. public class MinHeap {
  2.     int[]                    heapElem;
  3.     int                      size;
  4.     int                      maxSize;
  5.     private static final int FRONT = 1;
  6.  
  7.     public MinHeap(int maxsize) {
  8.         this.maxSize = maxsize;
  9.         this.size = 0;
  10.         heapElem = new int[this.maxSize + 1];
  11.         heapElem[0] = Integer.MIN_VALUE;
  12.     }
  13.  
  14.     int getParent(int pos) {
  15.         return pos / 2;
  16.     }
  17.  
  18.     int getLeft(int pos) {
  19.         return 2 * pos;
  20.     }
  21.  
  22.     int getRight(int pos) {
  23.         return 2 * pos + 1;
  24.     }
  25.  
  26.     boolean isLeaf(int pos) {
  27.         if (pos >= size / 2 && pos <= size) {
  28.             return true;
  29.         }
  30.         return false;
  31.     }
  32.  
  33.     void swapNode(int p1, int p2) {
  34.         int temp = heapElem[p1];
  35.         heapElem[p1] = heapElem[p2];
  36.         heapElem[p2] = temp;
  37.     }
  38.  
  39.     void minHeapify(int pos) {
  40.         if (!isLeaf(pos)) {
  41.             if (heapElem[pos] > heapElem[getLeft(pos)] || heapElem[pos] > heapElem[getRight(pos)]) {
  42.                 if (heapElem[getLeft(pos)] < heapElem[getRight(pos)]) {
  43.                     swapNode(pos, getLeft(pos));
  44.                     minHeapify(getLeft(pos));
  45.                 } else {
  46.                     swapNode(pos, getRight(pos));
  47.                     minHeapify(getRight(pos));
  48.                 }
  49.             }
  50.         }
  51.     }
  52.  
  53.     public void insert(int element) {
  54.         if (size >= maxSize) {
  55.             return;
  56.         }
  57.         heapElem[++size] = element;
  58.         int current = size;
  59.         while (heapElem[current] < getParent(current)) {
  60.             swapNode(current, getParent(current));
  61.             current = getParent(current);
  62.         }
  63.     }
  64.  
  65.     public int remove() {
  66.         int removed = heapElem[FRONT];
  67.         heapElem[FRONT] = heapElem[size--];
  68.         minHeapify(FRONT);
  69.         return removed;
  70.     }
  71.  
  72.     public void minHeap() {
  73.         for (int pos = (size / 2); pos >= 1; pos--) {
  74.             minHeapify(pos);
  75.         }
  76.     }
  77.  
  78.     public void print() {
  79.         for (int i = 1; i <= size / 2; i++) {
  80.             System.out.print(" PARENT : " + heapElem[i] + " LEFT CHILD : " + heapElem[2 * i] + " RIGHT CHILD :"
  81.                     + heapElem[2 * i + 1]);
  82.             System.out.println();
  83.         }
  84.     }
  85.  
  86.     // Driver code
  87.     public static void main(String[] arg) {
  88.         System.out.println("The Min Heap is ");
  89.         MinHeap minHeap = new MinHeap(15);
  90.         minHeap.insert(5);
  91.         minHeap.insert(3);
  92.         minHeap.insert(17);
  93.         minHeap.insert(10);
  94.         minHeap.insert(84);
  95.         minHeap.insert(19);
  96.         minHeap.insert(6);
  97.         minHeap.insert(22);
  98.         minHeap.insert(9);
  99.         minHeap.minHeap();
  100.  
  101.         minHeap.print();
  102.         System.out.println("The Min val is " + minHeap.remove());
  103.     }
  104.  
  105. }
Add Comment
Please, Sign In to add comment