1#include <stdio.h>
2#include <stdlib.h>
3#include <limits.h>
4
5struct HeapNode {
6    int val;
7    int r;
8    int c;
9};
10
11void minHeapify(struct HeapNode heap[], int i, int heap_size) {
12    int smallest = i;
13    int left = 2 * i + 1;
14    int right = 2 * i + 2;
15
16    if (left < heap_size && heap[left].val < heap[smallest].val)
17        smallest = left;
18    if (right < heap_size && heap[right].val < heap[smallest].val)
19        smallest = right;
20    if (smallest != i) {
21        struct HeapNode temp = heap[i];
22        heap[i] = heap[smallest];
23        heap[smallest] = temp;
24        minHeapify(heap, smallest, heap_size);
25    }
26}
27
28int kthSmallest(int** matrix, int n, int k) {
29    struct HeapNode* heap = malloc(n * sizeof(struct HeapNode));
30    for (int i = 0; i < n; i++) {
31        heap[i].val = matrix[i][0];
32        heap[i].r = i;
33        heap[i].c = 0;
34    }
35
36    for (int i = n / 2 - 1; i >= 0; i--)
37        minHeapify(heap, i, n);
38
39    struct HeapNode hr;
40    for (int i = 0; i < k; i++) {
41        hr = heap[0];
42        int nextVal = (hr.c < n - 1) ? matrix[hr.r][hr.c + 1] : INT_MAX;
43        heap[0].val = nextVal;
44        heap[0].c += 1;
45        minHeapify(heap, 0, n);
46    }
47
48    int result = hr.val;
49    free(heap);
50    return result;
51}
52
53int main() {
54    int* matrix[3];
55    int a[] = {1, 5, 9};
56    int b[] = {10, 11, 13};
57    int c[] = {12, 13, 15};
58    matrix[0] = a;
59    matrix[1] = b;
60    matrix[2] = c;
61    printf("%d\n", kthSmallest(matrix, 3, 8));
62    return 0;
63}