fork(1) download
  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
stdin
Standard input is empty
stdout
1  2  3  3  4  4  5  5  5  6  7  7  7  8  8  9  10  11  13  45