Tuesday 20 September 2016

Implement Max-Heap in java

It provides constant time retrieval and logarithmic time removal of both the minimum and maximum elements in it.

This makes the min-max heap a very useful data structure to implement double-ended priority queue. Like binary min-heaps and max-heaps, min-max heaps support O(logn) insertion and deletion, can be built in time O (n)  and are often represented implicitly in an array.

public class MaxHeap {

      private int size;
      private int[] maxHeap;
      private static final int START_IDX = 1;

      public MaxHeap(int mSize) {
            this.maxHeap = new int[mSize+1];
      }

     
      /**
       * 1. Insert the element at the last position.
       * 2. Check whether the parent is smaller.
       * 3. Swap Child and Parent.
       * 4. Keep iterate the same till the Max-Heap property doesn't match.
       * @param element
       */
      private void insert(int element) {
            maxHeap[++size] = element;
            int currIdx = size;
            while(currIdx>1 && maxHeap[currIdx]>maxHeap[parent(currIdx)]) {
                  swapElement(currIdx,parent(currIdx));
                  currIdx = parent(currIdx);
            }
      }

      /**
       * Swap two elements.
       * @param currIdx
       * @param parent
       */
      private void swapElement(int currIdx, int parent) {
            int temp = maxHeap[currIdx];
            maxHeap[currIdx] = maxHeap[parent];
            maxHeap[parent] = temp;
      }

      /**
       * 1. Store the top element.
       * 2. Replace it with last element and reduce the heap size by 1.
       * 3. Heapify to restore the max heap property.
       */
      private void remove() {
            int max = maxHeap[START_IDX];

            /**Put the last element on the TOP and Heapify it.*/
            maxHeap[START_IDX] = maxHeap[size--];
           
            maxHeapify(START_IDX);

            System.out.println("Maximum element:"+max);
      }

      /**
       * Heapify to get back Max-Heap.
       * @param indx
       */
      private void maxHeapify(int indx) {
            if(!isLeaf(indx)) {
                 
                  /** To check left and right child element.
                   * If greater then heapify. */
                  if(maxHeap[indx]<maxHeap[leftChild(indx)] ||
                              maxHeap[indx]<maxHeap[rightChild(indx)]) {
                       
                        /** Heapify the left Max-Heap. */
                        if(maxHeap[indx]<maxHeap[leftChild(indx)]) {
                              swapElement(indx, leftChild(indx));
                              maxHeapify(leftChild(indx));
                        } else {
                              swapElement(indx, rightChild(indx));
                              maxHeapify(rightChild(indx));
                        }
                  }
            }
      }

      /**
       * Return parent index of child index.
       * @param indx
       * @return  parent index.
       */
      private int parent(int currIdx) {
            return currIdx/2;
      }
     
      /**
       * Return right child index.
       * @param indx
       * @return right child index.
       */
      private int rightChild(int indx) {
            return indx*2+1;
      }

      /**
       * Return left child index.
       * @param indx
       * @return left child index.
       */
      private int leftChild(int indx) {
            return indx*2;
      }

      /**
       * To check whether the index is leaf or not.
       * @param indx
       * @return boolean value.
       */
      private boolean isLeaf(int indx) {
            if (indx>=(size/2) && indx<=size) {
                  return true;
            }
            return false;
      }

      /**
       * Utility to print the Max-Heap elements. 
       */
      private void printMaxHeap() {
            for (int i = 1; i <= size / 2; i++ ) {
                  StringBuffer sb = new StringBuffer("Perent: "+maxHeap[i]);
                  if(size>=2*i) {
                        sb.append(" Left: "+ maxHeap[2*i]);
                  }
                  if(size>=2*i+1) {
                        sb.append(" Right:"+maxHeap[2*i+1]);
                  }
                  System.out.print(sb.toString());
                  System.out.println();
            }
      }
     
      public static void main(String[] args) {

            MaxHeap heap = new MaxHeap(10);

            heap.insert(5);
            heap.insert(3);
            heap.insert(17);
            heap.insert(10);
            heap.insert(84);
            heap.insert(19);
            heap.insert(6);
            heap.insert(22);
            heap.insert(9);
     
            heap.remove();
           
            heap.printMaxHeap();
      }
     
}

No comments:

Post a Comment

Related Posts Plugin for WordPress, Blogger...