PU Find K Pairs with Smallest Sums

/**
 * Return an array of arrays of size *returnSize.
 * The sizes of the arrays are returned as *columnSizes array.
 * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
 */
struct Heap {
    int *vals;
    int *left;
    int *right;
    int top;
    int size;
};

struct Heap *create() {
    struct Heap *obj = malloc(sizeof(struct Heap));
    obj->size = 1000;
    obj->vals = malloc(obj->size * sizeof(int));
    obj->left = malloc(obj->size * sizeof(int));
    obj->right = malloc(obj->size * sizeof(int));
    obj->top = 1;
    return obj;
}

void push(struct Heap *heap, int val, int r, int c) {
    if (heap->size == heap->top) {
        heap->size += 1000;
        heap->vals = realloc(heap->vals, heap->size * sizeof(int));
        heap->left = realloc(heap->left, heap->size * sizeof(int));
        heap->right = realloc(heap->right, heap->size * sizeof(int));
    }
    heap->vals[heap->top] = val;
    heap->left[heap->top] = r;
    heap->right[heap->top] = c;
    int cur = heap->top++, root = cur / 2;
    while (root && heap->vals[root] > heap->vals[cur]) {
        int tmp = heap->vals[root];
        heap->vals[root] = heap->vals[cur];
        heap->vals[cur] = tmp;
        tmp = heap->left[root];
        heap->left[root] = heap->left[cur];
        heap->left[cur] = tmp;
        tmp = heap->right[root];
        heap->right[root] = heap->right[cur];
        heap->right[cur] = tmp;
        cur = root;
        root = cur / 2;
    }
}

void pop(struct Heap *heap, int *r, int *c) {
    *r = heap->left[1];
    *c = heap->right[1];
    heap->vals[1] = heap->vals[--heap->top];
    heap->left[1] = heap->left[heap->top];
    heap->right[1] = heap->right[heap->top];
    int root = 1, left = 2, right = 3;
    while (left < heap->top) {
        int target = left;
        if (right < heap->top && heap->vals[right] < heap->vals[left]) {
            target = right;
        }
        if (heap->vals[root] <= heap->vals[target]) return;

        int tmp = heap->vals[root];
        heap->vals[root] = heap->vals[target];
        heap->vals[target] = tmp;

        tmp = heap->left[root];
        heap->left[root] = heap->left[target];
        heap->left[target] = tmp;

        tmp = heap->right[root];
        heap->right[root] = heap->right[target];
        heap->right[target] = tmp;

        root = target;
        left = root * 2;
        right = left + 1;
    }
}

int** kSmallestPairs(int* nums1, int nums1Size, int* nums2, int nums2Size, int k, int** columnSizes, int* returnSize) {
    if (!nums1  || !nums1Size || !nums2 || !nums2Size) return 0;

    int **res = malloc(k * sizeof(int *));
    *columnSizes = malloc(k * sizeof(int));
    *returnSize = 0;

    struct Heap *heap = create();
    int r = 0, c = 0;
    push(heap, nums1[r] + nums2[c], r, c);
    int i;
    for (i = 0; i < k && heap->top > 1; i++) {
        pop(heap, &r, &c);
        res[*returnSize] = malloc(2 * sizeof(int));
        res[*returnSize][0] = nums1[r];
        res[*returnSize][1] = nums2[c];
        (*columnSizes)[*returnSize] = 2;
        ++*returnSize;
        if (r < nums1Size - 1) push(heap, nums1[r + 1] + nums2[c], r + 1, c);
        if (!r && c < nums2Size - 1) push(heap, nums1[r] + nums2[c + 1], r, c + 1);
    }
    return res;
}