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

      }

     

}