Thursday, 11 February 2016

Min Heap using Java.....

here is the code....


       

public class BuildMinHeapProblem {
 static int[] heap = {
  80,
  90,
  32,
  1,
  40,
  50,
  45,
  22,
  12,
  23,
  33
 };
 static int smallest;
 static int left; //left child index
 static int right; //right child index
 static int temp;

 public static void main(String[] args) {
  buildMinHeap();
  for (int k: heap) {
   System.out.print(k);
   System.out.print(" ");
  }
 }
 public static void buildMinHeap() {
  for (int p = heap.length / 2 - 1; p >= 0; p--) {
   min_Heapify(p);
  }
 }
 public static void min_Heapify(int p) {
  left = leftChild(p);
  right = rightChild(p);

  if ((left < heap.length) && (heap[left] < heap[p]))
   smallest = left;
  else smallest = p;

  if ((right < heap.length) && (heap[right] < heap[smallest]))
   smallest = right;

  if (smallest != p) {
   swap(smallest, p);
   min_Heapify(smallest);
  }
 }
 public static int leftChild(int k) {
  return (2 * k + 1);
 }
 public static int rightChild(int i) {
  return (2 * i + 2);
 }
 public static void swap(int a, int b) {
  temp = heap[a];
  heap[a] = heap[b];
  heap[b] = temp;
 }

}
       
 

No comments:

Post a Comment