#include <stdio.h>
#include <stdlib.h>
#define INT_MAX 1000
typedef struct heap_node{
int data;
int array_no;
int item_no;
} heap_node ;
int left_child(int i){
return (i*2)+1;
}
int right_child(int i){
return (2*i)+2;
}
heap_node * create_node(int data, int arr_no, int item_no){
heap_node
*node
= (heap_node
*)(malloc)(sizeof(heap_node
)); if(node){
node->data = data;
node->array_no = arr_no;
node->item_no = item_no;
}
return node;
}
void swap_ptr(heap_node * a[], int i, int j){
heap_node * temp = a[i];
a[i] = a[j];
a[j] = temp;
}
void min_heapify_ptr(heap_node * a[], int i, int len){
int smallest =i;
int left, right;
left = left_child(i);
right = right_child(i);
if(left <= len && a[i]->data >a[left]->data){
smallest = left;
}
if(right <= len && a[smallest]->data > a[right]->data){
smallest = right;
}
if(smallest != i){
swap_ptr(a, i, smallest);
min_heapify_ptr(a, smallest, len);
}
}
void build_heap_ptr(heap_node *a[], int len){
int i = len/2 +1;
for(; i>=0; i--){
min_heapify_ptr(a,i, len);
}
}
void merge(int a[5][5], int N, int K, int result[]){
int i;
heap_node *min_heap[K];
/* Put all elements in an array */
for(i=0;i<K; i++){
min_heap[i] = create_node(a[i][0],i, 0);
}
/* Build min heap with those entered elements */
build_heap_ptr(min_heap,K-1);
/* Now we have to take every element one by one and replace root with that and heapify again */
for(i=0; i<N*K; i++){
heap_node * min_node = min_heap[0];
/* Put the root of min heap in result array */
result[i] = min_node->data;
/* If there are elements to be considered in that array */
if(min_node->item_no + 1< N){
min_heap[0] = create_node(a[min_node->array_no][min_node->item_no + 1], min_node->array_no, min_node->item_no + 1);
}
/* else put INT_MAX at root */
else
{
min_heap[0] = create_node(INT_MAX, min_node->array_no, min_node->item_no + 1);
}
/* Heapify again */
min_heapify_ptr(min_heap, 0,K-1);
}
}
int main(void) {
// your code goes here
int i;
int K= 4;
int N =5;
int a[5][5] = {2,3,5,6,7,
4,7,8,9,10,
3,5,11,13,45,
1,4,5,7,8};
int result[N*K];
merge(a,N, K, result);
for(i=0; i<N*K; i++){
}
return 0;
}
I2luY2x1ZGUgPHN0ZGlvLmg+CiNpbmNsdWRlIDxzdGRsaWIuaD4KI2RlZmluZSBJTlRfTUFYIDEwMDAKCnR5cGVkZWYgc3RydWN0IGhlYXBfbm9kZXsKICAgICAgICBpbnQgZGF0YTsKICAgICAgICBpbnQgYXJyYXlfbm87CiAgICAgICAgaW50IGl0ZW1fbm87Cn0gaGVhcF9ub2RlIDsKaW50IGxlZnRfY2hpbGQoaW50IGkpewogICAgICAgIHJldHVybiAoaSoyKSsxOwp9CmludCByaWdodF9jaGlsZChpbnQgaSl7CiAgICAgICAgcmV0dXJuICgyKmkpKzI7Cn0KaGVhcF9ub2RlICogY3JlYXRlX25vZGUoaW50IGRhdGEsIGludCBhcnJfbm8sIGludCBpdGVtX25vKXsKICAgICAgICBoZWFwX25vZGUgKm5vZGUgPSAoaGVhcF9ub2RlICopKG1hbGxvYykoc2l6ZW9mKGhlYXBfbm9kZSkpOwogICAgICAgIGlmKG5vZGUpewogICAgICAgICAgICAgICAgbm9kZS0+ZGF0YSA9IGRhdGE7CiAgICAgICAgICAgICAgICBub2RlLT5hcnJheV9ubyA9IGFycl9ubzsKICAgICAgICAgICAgICAgIG5vZGUtPml0ZW1fbm8gPSBpdGVtX25vOwogICAgICAgIH0KICAgICAgICByZXR1cm4gbm9kZTsKCn0Kdm9pZCBzd2FwX3B0cihoZWFwX25vZGUgKiBhW10sIGludCBpLCBpbnQgail7CiAgICAgICAgaGVhcF9ub2RlICogdGVtcCA9IGFbaV07CiAgICAgICAgYVtpXSA9IGFbal07CiAgICAgICAgYVtqXSA9IHRlbXA7ICAgIAp9Cgp2b2lkIG1pbl9oZWFwaWZ5X3B0cihoZWFwX25vZGUgKiBhW10sIGludCBpLCBpbnQgbGVuKXsKICAgICAgICBpbnQgc21hbGxlc3QgPWk7CiAgICAgICAgaW50IGxlZnQsIHJpZ2h0OwoKICAgICAgICBsZWZ0ID0gbGVmdF9jaGlsZChpKTsKICAgICAgICByaWdodCA9IHJpZ2h0X2NoaWxkKGkpOwogICAgICAgIGlmKGxlZnQgPD0gbGVuICYmIGFbaV0tPmRhdGEgPmFbbGVmdF0tPmRhdGEpewogICAgICAgICAgICAgICAgc21hbGxlc3QgPSBsZWZ0OwogICAgICAgIH0KICAgICAgICBpZihyaWdodCA8PSBsZW4gJiYgYVtzbWFsbGVzdF0tPmRhdGEgPiBhW3JpZ2h0XS0+ZGF0YSl7CiAgICAgICAgICAgICAgICBzbWFsbGVzdCA9IHJpZ2h0OwogICAgICAgIH0KICAgICAgICBpZihzbWFsbGVzdCAhPSBpKXsKICAgICAgICAgICAgICAgIHN3YXBfcHRyKGEsIGksIHNtYWxsZXN0KTsKICAgICAgICAgICAgICAgIG1pbl9oZWFwaWZ5X3B0cihhLCBzbWFsbGVzdCwgbGVuKTsKICAgICAgICB9Cn0Kdm9pZCBidWlsZF9oZWFwX3B0cihoZWFwX25vZGUgKmFbXSwgaW50IGxlbil7CiAgICAgICAgaW50IGkgPSBsZW4vMiArMTsKICAgICAgICBmb3IoOyBpPj0wOyBpLS0pewogICAgICAgICAgICAgICAgbWluX2hlYXBpZnlfcHRyKGEsaSwgbGVuKTsKICAgICAgICB9Cn0Kdm9pZCBtZXJnZShpbnQgYVs1XVs1XSwgaW50IE4sIGludCBLLCBpbnQgcmVzdWx0W10pewogICAgICAgIGludCBpOwogICAgICAgIGhlYXBfbm9kZSAqbWluX2hlYXBbS107Ci8qIFB1dCBhbGwgZWxlbWVudHMgaW4gYW4gYXJyYXkgKi8KICAgICAgICBmb3IoaT0wO2k8SzsgaSsrKXsKICAgICAgICAgICAgICAgIG1pbl9oZWFwW2ldID0gY3JlYXRlX25vZGUoYVtpXVswXSxpLCAwKTsKICAgICAgICB9CgogLyogQnVpbGQgbWluIGhlYXAgd2l0aCB0aG9zZSBlbnRlcmVkIGVsZW1lbnRzICovCiAgICAgICAgYnVpbGRfaGVhcF9wdHIobWluX2hlYXAsSy0xKTsKICAgICAgICAKLyogTm93IHdlIGhhdmUgdG8gdGFrZSBldmVyeSBlbGVtZW50IG9uZSBieSBvbmUgYW5kIHJlcGxhY2Ugcm9vdCB3aXRoIHRoYXQgYW5kIGhlYXBpZnkgYWdhaW4gKi8gCiAgIGZvcihpPTA7IGk8TipLOyBpKyspewogICAgICAgICAgICAgICAgCiAgICAgICAgIGhlYXBfbm9kZSAqIG1pbl9ub2RlID0gbWluX2hlYXBbMF07CiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAKICAgICAgIC8qIFB1dCB0aGUgcm9vdCBvZiBtaW4gaGVhcCBpbiByZXN1bHQgYXJyYXkgKi8KICAgICAgICAgcmVzdWx0W2ldID0gbWluX25vZGUtPmRhdGE7CiAgICAgICAvKiBJZiB0aGVyZSBhcmUgZWxlbWVudHMgdG8gYmUgY29uc2lkZXJlZCBpbiB0aGF0IGFycmF5ICovCiAgICAgICAgaWYobWluX25vZGUtPml0ZW1fbm8gKyAxPCBOKXsKICAgICAgICBtaW5faGVhcFswXSA9IGNyZWF0ZV9ub2RlKGFbbWluX25vZGUtPmFycmF5X25vXVttaW5fbm9kZS0+aXRlbV9ubyAgICAgICAgICAgICAgICAgICAgICAgICArIDFdLCBtaW5fbm9kZS0+YXJyYXlfbm8sIG1pbl9ub2RlLT5pdGVtX25vICsgMSk7CiAgICAgICAgfSAgICAgICAKICAgICAgICAvKiBlbHNlIHB1dCBJTlRfTUFYIGF0IHJvb3QgKi8KICAgICAgICBlbHNlCiAgICAgICAgewogICAgICAgICAgbWluX2hlYXBbMF0gPSBjcmVhdGVfbm9kZShJTlRfTUFYLCBtaW5fbm9kZS0+YXJyYXlfbm8sICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIG1pbl9ub2RlLT5pdGVtX25vICsgMSk7CiAgICAgICAgfQogICAgICAgIC8qIEhlYXBpZnkgYWdhaW4gKi8KICAgICAgICAgbWluX2hlYXBpZnlfcHRyKG1pbl9oZWFwLCAwLEstMSk7CiAgIH0gICAgICAgCgp9CgppbnQgbWFpbih2b2lkKSB7CgkvLyB5b3VyIGNvZGUgZ29lcyBoZXJlCglpbnQgaTsKCWludCBLPSA0OwogICAgaW50IE4gPTU7IAogICAgaW50IGFbNV1bNV0gPSB7MiwzLDUsNiw3LAogICAgICAgICAgICAgICAgICAgICAgICA0LDcsOCw5LDEwLAogICAgICAgICAgICAgICAgICAgICAgICAzLDUsMTEsMTMsNDUsCiAgICAgICAgICAgICAgICAgICAgICAgIDEsNCw1LDcsOH07CgogICAgaW50IHJlc3VsdFtOKktdOwogICAgbWVyZ2UoYSxOLCBLLCByZXN1bHQpOyAgICAgICAgICAKICAgIHByaW50ZigiXG4iKTsKICAgIGZvcihpPTA7IGk8TipLOyBpKyspewogICAgICAgICBwcmludGYoIiVkICAiLCByZXN1bHRbaV0pOwogICAgfQogICAgcmV0dXJuIDA7Cn0KCg==