Print all elements in sorted order from row and column wise sorted matrix
Given an n x n matrix, where every row and column is sorted in non-decreasing order. Print all elements of the matrix in sorted order.
Example:
Input: mat[][] = { {10, 20, 30, 40},
{15, 25, 35, 45},
{27, 29, 37, 48},
{32, 33, 39, 50},
};
Output: 10 15 20 25 27 29 30 32 33 35 37 39 40 45 48 50
We can use Young Tableau to solve the above problem. The idea is to consider the given 2D array as Young Tableau and call extract minimum O(N)
Algorithm:
- Define a constant INF equal to INT_MAX and N equal to the size of the matrix.
- Implement a youngify function that takes a 2D matrix and two integer values i and j as input parameters.
- In the youngify function, find the values at the down and right sides of mat[i][j].
- If mat[i][j] is the down right corner element, then return.
- Move the smaller of two values (downVal and rightVal) to mat[i][j] and recursively call youngify for the smaller value.
- Implement an extractMin function that takes a 2D matrix as an input parameter.
- In the extractMin function, store the value at mat[0][0] in a variable ret and update mat[0][0] with INF.
- Recursively call youngify with the starting cell (0, 0).
- Return the value stored in ret.
- Implement a printSorted function that takes a 2D matrix as an input parameter.
- Iterate N*N times and call extractMin each time and print the returned value.
- Implement the main function.
- Declare a 2D matrix mat of size NxN and initialize it with values.
- Call the printSorted function with mat as an input parameter.
- Return 0
Below is the implementation of this approach:
C++
// A C++ program to Print all elements in sorted order from row and // column wise sorted matrix #include<iostream> #include<climits> using namespace std; #define INF INT_MAX #define N 4 // A utility function to youngify a Young Tableau. This is different // from standard youngify. It assumes that the value at mat[0][0] is // infinite. void youngify( int mat[][N], int i, int j) { // Find the values at down and right sides of mat[i][j] int downVal = (i+1 < N)? mat[i+1][j]: INF; int rightVal = (j+1 < N)? mat[i][j+1]: INF; // If mat[i][j] is the down right corner element, return if (downVal==INF && rightVal==INF) return ; // Move the smaller of two values (downVal and rightVal) to // mat[i][j] and recur for smaller value if (downVal < rightVal) { mat[i][j] = downVal; mat[i+1][j] = INF; youngify(mat, i+1, j); } else { mat[i][j] = rightVal; mat[i][j+1] = INF; youngify(mat, i, j+1); } } // A utility function to extract minimum element from Young tableau int extractMin( int mat[][N]) { int ret = mat[0][0]; mat[0][0] = INF; youngify(mat, 0, 0); return ret; } // This function uses extractMin() to print elements in sorted order void printSorted( int mat[][N]) { for ( int i=0; i<N*N; i++) cout << extractMin(mat) << " " ; } // driver program to test above function int main() { int mat[N][N] = { {10, 20, 30, 40}, {15, 25, 35, 45}, {27, 29, 37, 48}, {32, 33, 39, 50}, }; printSorted(mat); return 0; } |
Java
// A Java program to Print all elements // in sorted order from row and // column wise sorted matrix import java.io.*; public class GFG { static final int INF = Integer.MAX_VALUE; static final int N = 4 ; // A utility function to youngify a Young Tableau. // This is different from standard youngify. // It assumes that the value at mat[0][0] is infinite. static void youngify( int mat[][], int i, int j) { // Find the values at down and right sides of mat[i][j] int downVal = (i + 1 < N) ? mat[i + 1 ][j] : INF; int rightVal = (j + 1 < N) ? mat[i][j + 1 ] : INF; // If mat[i][j] is the down right corner element, // return if (downVal == INF && rightVal == INF) { return ; } // Move the smaller of two values // (downVal and rightVal) to mat[i][j] // and recur for smaller value if (downVal < rightVal) { mat[i][j] = downVal; mat[i + 1 ][j] = INF; youngify(mat, i + 1 , j); } else { mat[i][j] = rightVal; mat[i][j + 1 ] = INF; youngify(mat, i, j + 1 ); } } // A utility function to extract // minimum element from Young tableau static int extractMin( int mat[][]) { int ret = mat[ 0 ][ 0 ]; mat[ 0 ][ 0 ] = INF; youngify(mat, 0 , 0 ); return ret; } // This function uses extractMin() // to print elements in sorted order static void printSorted( int mat[][]) { System.out.println( "Elements of matrix in sorted order n" ); for ( int i = 0 ; i < N * N; i++) { System.out.print(extractMin(mat) + " " ); } } // Driver Code public static void main(String args[]) { int mat[][] = {{ 10 , 20 , 30 , 40 }, { 15 , 25 , 35 , 45 }, { 27 , 29 , 37 , 48 }, { 32 , 33 , 39 , 50 }}; printSorted(mat); } } // This code is contributed by Rajput-Ji |
Python3
# Python 3 program to Print all elements # in sorted order from row and column # wise sorted matrix import sys INF = sys.maxsize N = 4 # A utility function to youngify a Young # Tableau. This is different from standard # youngify. It assumes that the value at # mat[0][0] is infinite. def youngify(mat, i, j): # Find the values at down and # right sides of mat[i][j] downVal = mat[i + 1 ][j] if (i + 1 < N) else INF rightVal = mat[i][j + 1 ] if (j + 1 < N) else INF # If mat[i][j] is the down right # corner element, return if (downVal = = INF and rightVal = = INF): return # Move the smaller of two values # (downVal and rightVal) to mat[i][j] # and recur for smaller value if (downVal < rightVal): mat[i][j] = downVal mat[i + 1 ][j] = INF youngify(mat, i + 1 , j) else : mat[i][j] = rightVal mat[i][j + 1 ] = INF youngify(mat, i, j + 1 ) # A utility function to extract minimum # element from Young tableau def extractMin(mat): ret = mat[ 0 ][ 0 ] mat[ 0 ][ 0 ] = INF youngify(mat, 0 , 0 ) return ret # This function uses extractMin() to # print elements in sorted order def printSorted(mat): print ( "Elements of matrix in sorted order n" ) i = 0 while i < N * N: print (extractMin(mat), end = " " ) i + = 1 # Driver Code if __name__ = = "__main__" : mat = [[ 10 , 20 , 30 , 40 ], [ 15 , 25 , 35 , 45 ], [ 27 , 29 , 37 , 48 ], [ 32 , 33 , 39 , 50 ]] printSorted(mat) # This code is contributed by ita_c |
C#
// A C# program to Print all elements // in sorted order from row and // column wise sorted matrix using System; class GFG { static int INF = int .MaxValue; static int N = 4; // A utility function to youngify a Young Tableau. // This is different from standard youngify. // It assumes that the value at mat[0][0] is infinite. static void youngify( int [,]mat, int i, int j) { // Find the values at down and right sides of mat[i][j] int downVal = (i + 1 < N) ? mat[i + 1,j] : INF; int rightVal = (j + 1 < N) ? mat[i,j + 1] : INF; // If mat[i][j] is the down right corner element, // return if (downVal == INF && rightVal == INF) { return ; } // Move the smaller of two values // (downVal and rightVal) to mat[i][j] // and recur for smaller value if (downVal < rightVal) { mat[i,j] = downVal; mat[i + 1,j] = INF; youngify(mat, i + 1, j); } else { mat[i, j] = rightVal; mat[i, j + 1] = INF; youngify(mat, i, j + 1); } } // A utility function to extract // minimum element from Young tableau static int extractMin( int [,]mat) { int ret = mat[0,0]; mat[0, 0] = INF; youngify(mat, 0, 0); return ret; } // This function uses extractMin() // to print elements in sorted order static void printSorted( int [,]mat) { Console.WriteLine( "Elements of matrix in sorted order n" ); for ( int i = 0; i < N * N; i++) { Console.Write(extractMin(mat) + " " ); } } // Driver Code static public void Main () { int [,]mat = {{10, 20, 30, 40}, {15, 25, 35, 45}, {27, 29, 37, 48}, {32, 33, 39, 50}}; printSorted(mat); } } // This code is contributed by ajit. |
Javascript
<script> // A Javascript program to Print all elements // in sorted order from row and // column wise sorted matrix let INF = Number.MAX_VALUE; let N = 4; // A utility function to youngify a Young Tableau. // This is different from standard youngify. // It assumes that the value at mat[0][0] is infinite. function youngify(mat,i,j) { // Find the values at down and right sides of mat[i][j] let downVal = (i + 1 < N) ? mat[i + 1][j] : INF; let rightVal = (j + 1 < N) ? mat[i][j + 1] : INF; // If mat[i][j] is the down right corner element, // return if (downVal == INF && rightVal == INF) { return ; } // Move the smaller of two values // (downVal and rightVal) to mat[i][j] // and recur for smaller value if (downVal < rightVal) { mat[i][j] = downVal; mat[i + 1][j] = INF; youngify(mat, i + 1, j); } else { mat[i][j] = rightVal; mat[i][j + 1] = INF; youngify(mat, i, j + 1); } } // A utility function to extract // minimum element from Young tableau function extractMin(mat) { let ret = mat[0][0]; mat[0][0] = INF; youngify(mat, 0, 0); return ret; } // This function uses extractMin() // to print elements in sorted order function printSorted(mat) { document.write( "Elements of matrix in sorted order n<br>" ); for (let i = 0; i < N * N; i++) { document.write(extractMin(mat) + " " ); } } let mat=[[10, 20, 30, 40],[15, 25, 35, 45], [27, 29, 37, 48],[32, 33, 39, 50]]; printSorted(mat); // This code is contributed by avanitrachhadiya2155 </script> |
10 15 20 25 27 29 30 32 33 35 37 39 40 45 48 50
Time complexity of extract minimum is O(N) and it is called O(N2) times. Therefore the overall time complexity is O(N3).
Auxiliary Space: O(N2)
Another approach: The idea is to keep all elements of the matrix in a one-dimensional array and then sort the array and print all values in it.
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h> using namespace std; // Function to print all elements of matrix in sorted orderd void sortedMatrix( int N, vector<vector< int > > Mat) { vector< int > temp; // Store all elements of matrix into temp for ( int i = 0; i < N; i++) { for ( int j = 0; j < N; j++) { temp.push_back(Mat[i][j]); } } // Sort the temp sort(temp.begin(), temp.end()); // Print the values of temp for ( int i = 0; i < temp.size(); i++) { cout << temp[i] << " " ; } } int main() { int N = 4; vector<vector< int > > Mat = { { 10, 20, 30, 40 }, { 15, 25, 35, 45 }, { 27, 29, 37, 48 }, { 32, 33, 39, 50 }, }; sortedMatrix(N, Mat); return 0; } // This code is contributed by pratiknawale999 |
Java
// A Java program to Print all elements // in sorted order from row and // column wise sorted matrix import java.io.*; import java.util.*; class GFG { // Function to print all elements of matrix in sorted orderd static void sortedMatrix( int N, int [][] mat) { List<Integer> temp = new ArrayList<Integer>(); // Store all elements of matrix into temp for ( int i = 0 ; i < N; i++) { for ( int j = 0 ; j < N; j++) { temp.add(mat[i][j]); } } // Sort the temp Collections.sort(temp); // Print the values of temp for ( int i = 0 ; i < temp.size(); i++) { System.out.print(temp.get(i)+ " " ); } } public static void main (String[] args) { int N = 4 ; int mat[][] = {{ 10 , 20 , 30 , 40 }, { 15 , 25 , 35 , 45 }, { 27 , 29 , 37 , 48 }, { 32 , 33 , 39 , 50 }}; sortedMatrix(N,mat); } } // This code is contributed by shruti456rawal |
Python3
# Function to print all elements of matrix in sorted orderd def sortedMatrix(N, Mat): temp = [] # Store all elements of matrix into temp for i in range ( 0 , N): for j in range ( 0 , N): temp.append(Mat[i][j]) # Sort the temp temp.sort() # Print the values of temp for i in range ( len (temp)): print (temp[i], end = ' ' ) if __name__ = = "__main__" : N = 4 Mat = [[ 10 , 20 , 30 , 40 ], [ 15 , 25 , 35 , 45 ], [ 27 , 29 , 37 , 48 ], [ 32 , 33 , 39 , 50 ]] sortedMatrix(N, list (Mat)) # This code is contributed by Aarti_Rathi |
C#
using System; using System.Collections.Generic; public static class GFG { // Function to print all elements of matrix in sorted // orderd static void sortedMatrix( int N, List<List< int > > Mat) { List< int > temp = new List< int >(); // Store all elements of matrix into temp for ( int i = 0; i < N; i++) { for ( int j = 0; j < N; j++) { temp.Add(Mat[i][j]); } } // Sort the temp temp.Sort(); // Print the values of temp for ( int i = 0; i < temp.Count; i++) { Console.Write(temp[i]); Console.Write( " " ); } } public static void Main() { int N = 4; List<List< int > > Mat = new List<List< int > >() { new List< int >{ 10, 20, 30, 40 }, new List< int >{ 15, 25, 35, 45 }, new List< int >{ 27, 29, 37, 48 }, new List< int > { 32, 33, 39, 50 } }; sortedMatrix(N, new List<List< int > >(Mat)); } // This code is contributed by Aarti_Rathi } |
Javascript
// A JavaScript program to Print all elements // in sorted order from row and // column wise sorted matrix // Function to print all elements of matrix in sorted orderd function sortedMatrix(N, mat) { var temp = []; // Store all elements of matrix into temp for ( var i=0; i < N; i++) { for ( var j=0; j < N; j++) { (temp.push(mat[i][j])); } } // Sort the temp temp.sort(); // Print the values of temp for ( var i =0; i < temp.length; i++) { console.log(temp[i] + " " ); } } var N = 4; var mat = [[10, 20, 30, 40], [15, 25, 35, 45], [27, 29, 37, 48], [32, 33, 39, 50]]; sortedMatrix(N, mat); // This code is contributed by Aarti_Rathi |
10 15 20 25 27 29 30 32 33 35 37 39 40 45 48 50
Time Complexity: O(N2log(N2))
Auxiliary Space: O(N2)
A better solution is to use the approach used for merging k sorted arrays. The idea is to use a Min Heap of size N which stores elements of first column. They do extract minimum. In extract minimum, replace the minimum element with the next element of the row from which the element is extracted.
C++
// C++ program to merge k sorted arrays of size n each. #include<iostream> #include<climits> using namespace std; #define N 4 // A min heap node struct MinHeapNode { int element; // The element to be stored int i; // index of the row from which the element is taken int j; // index of the next element to be picked from row }; // Prototype of a utility function to swap two min heap nodes void swap(MinHeapNode *x, MinHeapNode *y); // A class for Min Heap class MinHeap { MinHeapNode *harr; // pointer to array of elements in heap int heap_size; // size of min heap public : // Constructor: creates a min heap of given size MinHeap(MinHeapNode a[], int size); // to heapify a subtree with root at given index void MinHeapify( int ); // to get index of left child of node at index i int left( int i) { return (2*i + 1); } // to get index of right child of node at index i int right( int i) { return (2*i + 2); } // to get the root MinHeapNode getMin() { return harr[0]; } // to replace root with new node x and heapify() new root void replaceMin(MinHeapNode x) { harr[0] = x; MinHeapify(0); } }; // This function prints elements of a given matrix in non-decreasing // order. It assumes that ma[][] is sorted row wise sorted. void printSorted( int mat[][N]) { // Create a min heap with k heap nodes. Every heap node // has first element of an array MinHeapNode *harr = new MinHeapNode[N]; for ( int i = 0; i < N; i++) { harr[i].element = mat[i][0]; // Store the first element harr[i].i = i; // index of row harr[i].j = 1; // Index of next element to be stored from row } MinHeap hp(harr, N); // Create the min heap // Now one by one get the minimum element from min // heap and replace it with next element of its array for ( int count = 0; count < N*N; count++) { // Get the minimum element and store it in output MinHeapNode root = hp.getMin(); cout << root.element << " " ; // Find the next element that will replace current // root of heap. The next element belongs to same // array as the current root. if (root.j < N) { root.element = mat[root.i][root.j]; root.j += 1; } // If root was the last element of its array else root.element = INT_MAX; //INT_MAX is for infinite // Replace root with next element of array hp.replaceMin(root); } } // FOLLOWING ARE IMPLEMENTATIONS OF STANDARD MIN HEAP METHODS // FROM CORMEN BOOK // Constructor: Builds a heap from a given array a[] of given size MinHeap::MinHeap(MinHeapNode a[], int size) { heap_size = size; harr = a; // store address of array int i = (heap_size - 1)/2; while (i >= 0) { MinHeapify(i); i--; } } // A recursive method to heapify a subtree with root at given index // This method assumes that the subtrees are already heapified void MinHeap::MinHeapify( int i) { int l = left(i); int r = right(i); int smallest = i; if (l < heap_size && harr[l].element < harr[i].element) smallest = l; if (r < heap_size && harr[r].element < harr[smallest].element) smallest = r; if (smallest != i) { swap(&harr[i], &harr[smallest]); MinHeapify(smallest); } } // A utility function to swap two elements void swap(MinHeapNode *x, MinHeapNode *y) { MinHeapNode temp = *x; *x = *y; *y = temp; } // driver program to test above function int main() { int mat[N][N] = { {10, 20, 30, 40}, {15, 25, 35, 45}, {27, 29, 37, 48}, {32, 33, 39, 50}, }; printSorted(mat); return 0; } |
Python3
# Python code to merge k sorted arrays of size n each. N = 4 # A min heap node class MinHeapNode: def __init__( self , element, i, j): self .element = element # The element to be stored self .i = i # index of the row from which the element is taken self .j = j # index of the next element to be picked from row # A class for Min Heap class MinHeap: def __init__( self , a, size): self .harr = a # pointer to array of elements in heap self .heapSize = size # size of min heap # Build heap i = ( self .heapSize - 1 ) / / 2 while i > = 0 : self .minHeapify(i) i - = 1 def minHeapify( self , i): l = self .left(i) r = self .right(i) smallest = i if l < self .heapSize and self .harr[l].element < self .harr[i].element: smallest = l if r < self .heapSize and self .harr[r].element < self .harr[smallest].element: smallest = r if smallest ! = i: temp = self .harr[i] self .harr[i] = self .harr[smallest] self .harr[smallest] = temp self .minHeapify(smallest) # to get index of left child of node at index i def left( self , i): return 2 * i + 1 # to get index right child of node at index i def right( self , i): return 2 * i + 2 # to get the root def getMin( self ): return self .harr[ 0 ] # to replace root with new node x and heapify() new root def replaceMin( self , x): self .harr[ 0 ] = x self .minHeapify( 0 ) def swap(x, y): x.element, y.element = y.element, x.element # This function prints elements of a given matrix in non-decreasing # order. It assumes that ma[][] is sorted row wise sorted. def printSorted(mat): # Create a min heap with k heap nodes. Every heap node # has first element of an array harr = [MinHeapNode(mat[i][ 0 ], i, 1 ) for i in range (N)] heap = MinHeap(harr, N) # Create the min heap # Now one by one get the minimum element from min # heap and replace it with next element of its array for count in range (N * N): # Get the minimum element and store it in output root = heap.getMin() print (root.element, end = " " ) # Find the next element that will replace current # root of heap. The next element belongs to same # array as the current root. if (root.j < N): root.element = mat[root.i][root.j] root.j + = 1 # If root was the last element of its array else : root.element = float ( 'inf' ) # Replace root with next element of array heap.replaceMin(root) # Test mat = [ [ 10 , 20 , 30 , 40 ], [ 15 , 25 , 35 , 45 ], [ 27 , 29 , 37 , 48 ], [ 32 , 33 , 39 , 50 ] ] printSorted(mat) # This code is contributed by phasing17 |
Javascript
// JavaScript code to merge k sorted arrays of size n each. const N = 4; // A min heap node class MinHeapNode { constructor(element, i, j) { this .element = element; // The element to be stored this .i = i; // index of the row from which the element is taken this .j = j; // index of the next element to be picked from row } } // A class for Min Heap class MinHeap { constructor(a, size) { this .harr = a; // pointer to array of elements in heap this .heapSize = size; // size of min heap // Build heap let i = Math.floor(( this .heapSize - 1) / 2); while (i >= 0) { this .minHeapify(i); i--; } } // to heapify a subtree with root at given index minHeapify(i) { let l = this .left(i); let r = this .right(i); let smallest = i; if (l < this .heapSize && this .harr[l].element < this .harr[i].element) smallest = l; if (r < this .heapSize && this .harr[r].element < this .harr[smallest].element) smallest = r; if (smallest !== i) { let temp = this .harr[i]; this .harr[i] = this .harr[smallest]; this .harr[smallest] = temp; this .minHeapify(smallest); } } // to get index of left child of node at index i left(i) { return 2 * i + 1; } // to get index of right child of node at index i right(i) { return 2 * i + 2; } // to get the root getMin() { return this .harr[0]; } // to replace root with new node x and heapify() new root replaceMin(x) { this .harr[0] = x; this .minHeapify(0); } // Utility function to swap two elements swap(x, y) { let temp = x.element; x.element = y.element; y.element = temp; } } // This function prints elements of a given matrix in non-decreasing // order. It assumes that ma[][] is sorted row wise sorted. function printSorted(mat) { // Create a min heap with k heap nodes. Every heap node // has first element of an array let harr = new Array(N); for (let i = 0; i < N; i++) { harr[i] = new MinHeapNode(mat[i][0], i, 1); // Store the first element } let heap = new MinHeap(harr, N); // Create the min heap // Now one by one get the minimum element from min // heap and replace it with next element of its array for (let count = 0; count < N * N; count++) { // Get the minimum element and store it in output let root = heap.getMin(); console.log(root.element + " " ); // Find the next element that will replace current // root of heap. The next element belongs to same // array as the current root. if (root.j < N) { root.element = mat[root.i][root.j]; root.j += 1; } // If root was the last element of its array else root.element = Number.MAX_VALUE; //Number.MAX_VALUE is for infinite // Replace root with next element of array heap.replaceMin(root); } } // Test let mat = [ [10, 20, 30, 40], [15, 25, 35, 45], [27, 29, 37, 48], [32, 33, 39, 50] ]; printSorted(mat); // Expected output: 10 15 20 25 27 29 30 32 33 35 37 39 40 45 48 50 |
Java
import java.util.*; class MinHeapNode { int element; int i; int j; MinHeapNode( int element, int i, int j) { this .element = element; this .i = i; this .j = j; } } class MinHeap { int heapSize; MinHeapNode[] harr; MinHeap(MinHeapNode[] a, int size) { harr = a; heapSize = size; int i = (heapSize - 1 ) / 2 ; while (i >= 0 ) { minHeapify(i); i--; } } void minHeapify( int i) { int l = left(i); int r = right(i); int smallest = i; if (l < heapSize && harr[l].element < harr[i].element) { smallest = l; } if (r < heapSize && harr[r].element < harr[smallest].element) { smallest = r; } if (smallest != i) { MinHeapNode temp = harr[i]; harr[i] = harr[smallest]; harr[smallest] = temp; minHeapify(smallest); } } int left( int i) { return 2 * i + 1 ; } int right( int i) { return 2 * i + 2 ; } MinHeapNode getMin() { return harr[ 0 ]; } void replaceMin(MinHeapNode x) { harr[ 0 ] = x; minHeapify( 0 ); } } class Main { static int N = 4 ; static void printSorted( int [][] mat) { MinHeapNode[] harr = new MinHeapNode[N]; for ( int i = 0 ; i < N; i++) { harr[i] = new MinHeapNode(mat[i][ 0 ], i, 1 ); } MinHeap heap = new MinHeap(harr, N); for ( int count = 0 ; count < N * N; count++) { MinHeapNode root = heap.getMin(); System.out.print(root.element + " " ); if (root.j < N) { root.element = mat[root.i][root.j]; root.j += 1 ; } else { root.element = Integer.MAX_VALUE; } heap.replaceMin(root); } } public static void main(String[] args) { int [][] mat = { { 10 , 20 , 30 , 40 }, { 15 , 25 , 35 , 45 }, { 27 , 29 , 37 , 48 }, { 32 , 33 , 39 , 50 } }; printSorted(mat); } } // this code is added by devendrasalunke |
C#
using System; using System.Collections.Generic; // Define a class to represent a node in the min heap class MinHeapNode { public int element; // The value of the element in the node public int i; // The row index of the element in the matrix public int j; // The column index of the element in the matrix // Constructor to create a new node with the given values public MinHeapNode( int element, int i, int j) { this .element = element; this .i = i; this .j = j; } } // Define a class to represent a min heap data structure class MinHeap { public int heapSize; // The number of elements in the heap public MinHeapNode[] harr; // An array to store the heap elements // Constructor to create a new heap from the given array of nodes public MinHeap(MinHeapNode[] a, int size) { harr = a; heapSize = size; // Starting from the last non-leaf node and moving up, // apply the minHeapify operation to all nodes in the heap int i = (heapSize - 1) / 2; while (i >= 0) { minHeapify(i); i--; } } // Method to maintain the min heap property of the tree rooted at index i public void minHeapify( int i) { int l = left(i); int r = right(i); int smallest = i; // If the left child is smaller than the parent, mark it as the smallest if (l < heapSize && harr[l].element < harr[i].element) { smallest = l; } // If the right child is smaller than the smallest so far, mark it as the smallest if (r < heapSize && harr[r].element < harr[smallest].element) { smallest = r; } // If the smallest element is not the parent, swap it with the parent // and recursively apply minHeapify to the subtree rooted at the smallest element if (smallest != i) { MinHeapNode temp = harr[i]; harr[i] = harr[smallest]; harr[smallest] = temp; minHeapify(smallest); } } // Method to compute the index of the left child of a node at index i public int left( int i) { return 2 * i + 1; } // Method to compute the index of the right child of a node at index i public int right( int i) { return 2 * i + 2; } // Method to get the minimum element from the heap (i.e., the root of the tree) public MinHeapNode getMin() { return harr[0]; } // Method to replace the minimum element in the heap with a new element x, // and then restore the min heap property of the tree public void replaceMin(MinHeapNode x) { harr[0] = x; minHeapify(0); } } class Program { static int N = 4; static void printSorted( int [][] mat) { // Create a new MinHeapNode array and fill it with the first element from each row in the matrix. MinHeapNode[] harr = new MinHeapNode[N]; for ( int i = 0; i < N; i++) { harr[i] = new MinHeapNode(mat[i][0], i, 1); } // Create a new MinHeap and pass the array and its size to its constructor. MinHeap heap = new MinHeap(harr, N); // Traverse the entire matrix by looping N*N times for ( int count = 0; count < N * N; count++) { // Get the minimum element from the heap and print it MinHeapNode root = heap.getMin(); Console.Write(root.element + " " ); // If there are more elements in the row that contains the minimum element, // replace the minimum element in the heap with the next element in the row if (root.j < N) { root.element = mat[root.i][root.j]; root.j += 1; } else { // If we have reached the end of the row, replace the minimum element in the heap with infinity root.element = int .MaxValue; } // Replace the root with the new element in the heap heap.replaceMin(root); } } static void Main( string [] args) { // Initialize a 2D matrix int [][] mat = { new int []{10, 20, 30, 40}, new int []{15, 25, 35, 45}, new int []{27, 29, 37, 48}, new int []{32, 33, 39, 50} }; // Call the printSorted function with the matrix as argument printSorted(mat); } } |
10 15 20 25 27 29 30 32 33 35 37 39 40 45 48 50
Time complexity: O(N2LogN).
Auxiliary Space: O(N)
Exercise:
Above solutions work for a square matrix. Extend the above solutions to work for an M*N rectangular matrix.