fork(2) download
copy 
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #define INT_MAX 1000
  4.  
  5. typedef struct heap_node{
  6.         int data;
  7.         int array_no;
  8.         int item_no;
  9. } heap_node ;
  10. int left_child(int i){
  11.         return (i*2)+1;
  12. }
  13. int right_child(int i){
  14.         return (2*i)+2;
  15. }
  16. heap_node * create_node(int data, int arr_no, int item_no){
  17.         heap_node *node = (heap_node *)(malloc)(sizeof(heap_node));
  18.         if(node){
  19.                 node->data = data;
  20.                 node->array_no = arr_no;
  21.                 node->item_no = item_no;
  22.         }
  23.         return node;
  24.  
  25. }
  26. void swap_ptr(heap_node * a[], int i, int j){
  27.         heap_node * temp = a[i];
  28.         a[i] = a[j];
  29.         a[j] = temp;    
  30. }
  31.  
  32. void min_heapify_ptr(heap_node * a[], int i, int len){
  33.         int smallest =i;
  34.         int left, right;
  35.  
  36.         left = left_child(i);
  37.         right = right_child(i);
  38.         if(left <= len && a[i]->data >a[left]->data){
  39.                 smallest = left;
  40.         }
  41.         if(right <= len && a[smallest]->data > a[right]->data){
  42.                 smallest = right;
  43.         }
  44.         if(smallest != i){
  45.                 swap_ptr(a, i, smallest);
  46.                 min_heapify_ptr(a, smallest, len);
  47.         }
  48. }
  49. void build_heap_ptr(heap_node *a[], int len){
  50.         int i = len/2 +1;
  51.         for(; i>=0; i--){
  52.                 min_heapify_ptr(a,i, len);
  53.         }
  54. }
  55. void merge(int a[5][5], int N, int K, int result[]){
  56.         int i;
  57.         heap_node *min_heap[K];
  58. /* Put all elements in an array */
  59.         for(i=0;i<K; i++){
  60.                 min_heap[i] = create_node(a[i][0],i, 0);
  61.         }
  62.  
  63.  /* Build min heap with those entered elements */
  64.         build_heap_ptr(min_heap,K-1);
  65.  
  66. /* Now we have to take every element one by one and replace root with that and heapify again */ 
  67.    for(i=0; i<N*K; i++){
  68.  
  69.          heap_node * min_node = min_heap[0];
  70.  
  71.        /* Put the root of min heap in result array */
  72.          result[i] = min_node->data;
  73.        /* If there are elements to be considered in that array */
  74.         if(min_node->item_no + 1< N){
  75.         min_heap[0] = create_node(a[min_node->array_no][min_node->item_no                         + 1], min_node->array_no, min_node->item_no + 1);
  76.         }       
  77.         /* else put INT_MAX at root */
  78.         else
  79.         {
  80.           min_heap[0] = create_node(INT_MAX, min_node->array_no,                                              min_node->item_no + 1);
  81.         }
  82.         /* Heapify again */
  83.          min_heapify_ptr(min_heap, 0,K-1);
  84.    }       
  85.  
  86. }
  87.  
  88. int main(void) {
  89. 	// your code goes here
  90. 	int i;
  91. 	int K= 4;
  92.     int N =5; 
  93.     int a[5][5] = {2,3,5,6,7,
  94.                         4,7,8,9,10,
  95.                         3,5,11,13,45,
  96.                         1,4,5,7,8};
  97.  
  98.     int result[N*K];
  99.     merge(a,N, K, result);          
  100.     printf("\n");
  101.     for(i=0; i<N*K; i++){
  102.          printf("%d  ", result[i]);
  103.     }
  104.     return 0;
  105. }
  106.  
  107.  
Success #stdin #stdout 0s 2424KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1  2  3  3  4  4  5  5  5  6  7  7  7  8  8  9  10  11  13  45
https://ideone.com/0yeMCJ
Merge N sorted arrays in one sorted array
language:
C (gcc 8.3)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!