Tuesday 20 September 2016

Heapsort implementation in Java

Heapsort is a comparison-based sorting algorithm. It can be thought of as an improved selection sort: like that algorithm, it divides its input into a sorted and an unsorted region, and it iteratively shrinks the unsorted region by extracting the largest element and moving that to the sorted region.

The improvement consists of the use of a heap data structure rather than a linear-time search to find the maximum.

Although somewhat slower in practice on most machines than a well-implemented quicksort, it has the advantage of a more favorable worst-case O(n*logn) runtime.
Heapsort is an in-place algorithm, but it is not a stable sort.

public class HeapSort {

      /**
       * Heap sort logic.
       * @param array
       */
      private static void heapSort(int[] array) {
            int size = array.length;
           
            /** Heapify the complete array. */
            for (int i=size/2-1; i>=0; i--) {
                  heapify(array, i, size);
            }

            /**
             * 1. Swap the root element with last unsorted element.
             * 2. Heapify the array excluding the sorted sub-array.
             * 3. Repeat the step#1 and step#2.
             * */
            for (int i =size-1; i>=0; i--) {
                  int temp = array[0];
                  array[0] = array[i];
                  array[i] = temp;
                  heapify(array, 0, i);
            }
      }

      /**
       * To heapify a subtree rooted with node i which is an index in arr[]. n is size of heap
       * @param array
       * @param i
       * @param n
       */
      private static void heapify(int[] array, int i, int n) {

            int left = 2*i+1;
            int right = 2*i+2;

            int largest = i;

            /** Choose biggest element between left and right child. */
            if(left<n && array[largest]<array[left] ) {
                  largest = left;
            }
           
            if(right<n && array[largest]<array[right]) {
                  largest = right;
            }

            /**
             * 1. Swap the largest element to root.
             * 2. Heapify recursively.
             **/
            if (largest != i) {
                  swap(array,largest, i);
                  heapify(array, largest, n);
            }
      }


      public static void main(String args[]) {
           
            int[] array = {22, 19, 23, 15, 16, 17};
            heapSort(array);
           
            System.out.print("Sorted array is: ");
            printArray(array);
      }

      private static void printArray(int array[]) {
            int n = array.length;
            for (int i=0; i<n; i++) {
                  System.out.print(array[i]+" ");
            }
            System.out.println();
      }
     
      private static void swap(int[] array, int i, int j) {
            int temp = array[i];
            array[i] = array[j];
            array[j] = temp;
      }
}




Search in a row wise and column wise sorted matrix

1) Input matrix[n][n] and element e
2) Start with top right element
            i = 0; j= n-1;
3) while termination condition:
            a) if matrix[i][j]==e;
                        Return position
            b) matrix[i][j]<e then move it to down (i++)
            c) matrix[i][j]>e then move it to left (j--).
Repeat a, b and c.

Terminating conditions:
            1. element e found.
            2. i>=row or j<0

public class SearchSortMat {

      private static void findElement(int[][] matrix,int element) {
            int row = matrix.length;
            int i = 0;
            int j = matrix[0].length-1;

            while(i<row && j>=0) {
                  if(element == matrix[i][j]) {
                        System.out.println(element+" found at ("+i+","+j+")");
                        break;
                  } else if(element>matrix[i][j]) {
                        i++;
                  } else {
                        j--;
                  }
            }
            if(i>=row || j<0) {
                  System.out.println(element + " not found !!");
            }
      }

      public static void main(String[] args) {
            int[][] matrix = {{20, 30, 40, 50},
                        {25, 35, 45, 55},
                        {37, 39, 47, 58},
                        {42, 43, 49, 60}};

            int element = 43;

            findElement(matrix, element);
      }
}


Time Complexity: O(n)


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();
      }
     
}

Related Posts Plugin for WordPress, Blogger...