merge

#include <stdio.h>
#include <stdlib.h>

struct arr {
    int *a, min, k, cap;
};

struct queue {
    struct arr **heap;
    int cap, count;
};

struct queue initPriorityQueue (int);
void insert(struct queue *, struct arr *);
void swapQ(struct queue *, int, int);
void deleteMin (struct queue *);
void increaseKey (struct queue *);
void heapify(struct queue *, int);

int main(int argc, char *argv[]) {
    int k;
    scanf("%d", &k);
    int *arr = (int *)malloc(sizeof(int) * k);
    struct queue q = initPriorityQueue(k);
    for (int i = 0; i < k; i++) {
        scanf("%d", &arr[i]);
    }
    for (int i = 0; i < k; i++) {
        struct arr *elem = (struct arr *)malloc(sizeof(struct arr));
        elem->a = (int *)malloc(sizeof(int) * arr[i]);
        for (int j = 0; j < arr[i]; j++) {
            scanf("%d", &elem->a[j]);
        }
        elem->min = 0;
        elem->cap = arr[i];
        elem->k = elem->a[elem->min];
        insert (&q, elem);
        free(elem->a);
        free(elem);
    }
    while (q.count > 0) {
        printf("%d ", q.heap[0]->k);
        if (q.heap[0]->min == q.heap[0]->cap - 1){
            deleteMin(&q);
        } else {
            increaseKey(&q);
        }
    }
    free(q.heap);
    free(arr);
    return 0;
}

struct queue initPriorityQueue(int n){
    struct queue q;
    q.heap = (struct arr **)malloc(sizeof(struct arr *) * n);
    q.cap = n;
    q.count = 0;
    return q;
}

void insert (struct queue *q, struct arr *elem){
    int i = q->count;
    q->count++;
    q->heap[i] = elem;
    for (;i > 0 && q->heap[(i - 1) / 2]->k > q->heap[i]->k; i = (i - 1) / 2) {
        swapQ(q, i, (i - 1) / 2);
    }
}

void swapQ (struct queue *q, int i, int j){
    struct arr *t = q->heap[i];
    q->heap[i] = q->heap[j];
    q->heap[j] = t;
}

void increaseKey (struct queue *q){
    int i = q->heap[0]->min;
    q->heap[0]->min++;
    q->heap[0]->k = q->heap[0]->a[i + 1];
    heapify(q, 0);
}

void heapify(struct queue *q, int i){
    int l = 2 * i + 1;
    int r = 2 * i + 2;
    int largest;
    if (l < q->count && q->heap[l]->k < q->heap[i]->k){
        largest = l;
    }else largest = i;
    if (r < q->count && q->heap[r]->k < q->heap[largest]->k){
        largest = r;
    }
    if (largest != i){
        swapQ(q, i, largest);
        heapify(q, largest);
    }
}

void deleteMin (struct queue *q){
    q->count--;
    if (q->count > 0){
        q->heap[0] = q->heap[q->count];
        heapify(q, 0);
    }
}