Tuesday, 20 September 2016

Kth smallest element in a row-wise and column-wise sorted 2D array



Kth smallest element in a row-wise and column-wise sorted 2D array



Kth-smallest-element
Kth-smallest-element



#include<iostream>
#include<stdio.h>
#include<climits>
using namespace std;

typedef struct HeapNode
{
    int value;
    int row;
    int col;
}node;

void minHeapify(node arr[], int n ,int heap_size);
void swap_elements(node *x, node *y);
void  HeapSort(node arr[], int n);
int FindKthElement(int arr[4][4],int n,int k);




void swap_elements(node *x, node *y)
{
    node z = *x;
    *x= *y;
    *y=z;
}

void minHeapify(node arr[], int n ,int heap_size)
{
    int left = 2*n+1;
    int right = 2*n+2;
    int small =n;
    if(left<heap_size && arr[left].value < arr[n].value)
        small =left;
    if(right<heap_size && arr[right].value < arr[small].value)
        small =right;
    if(small !=n)
    {
        swap_elements(&arr[small], &arr[n]);
        minHeapify(arr,small,  heap_size);
    }

}

void  HeapSort(node arr[], int n)
{
    int i= (n-1)/2;
    while(i>=0)
    {
      minHeapify(arr, i, n);
      i--;
    }
}

int FindKthElement(int  arr[4][4],int n,int k)
{
    int next_value =0;
    if(k<=0 || k>n*n)
     return INT_MAX;


    node temp_Arr[n];
    /*creating heap for first row elements*/

   for (int i = 0; i < n; i++)
        temp_Arr[i] = {arr[0][i], 0, i};
    HeapSort(temp_Arr, n);

    node Next_value_array;

    for(int i=0;i<k;i++)
    {
        Next_value_array = temp_Arr[0];

        if(Next_value_array.row<(n-1))
        {
            next_value = arr[Next_value_array.row + 1][Next_value_array.col];
        }
        else
        {
            next_value = INT_MAX;
        }
        //int next_value = (Next_value_array.row<(n-1)) ? arr[Next_value_array.row + 1][Next_value_array.col]:INT_MAX;
        temp_Arr[0] =  {next_value, Next_value_array.row+1, Next_value_array.col };
        minHeapify(temp_Arr,0, n);
    }
    return Next_value_array.value;
}


int main()
{
    int arr[4][4] = { {10, 20, 30, 40},
                    {15, 25, 35, 45},
                    {25, 29, 37, 48},
                    {32, 33, 39, 50},
                  };
  cout << "7th smallest element is " << FindKthElement(arr, 4, 7);
  return 0;
}



Other Articles:


Other Blogs: Click here

0 comments:

Post a comment