easy heap solution C | Runtime Beats 100.00% | Memory Beats 100.00%
Complexity
Time complexity: O(nlogn)
Space complexity: O(n)
Code
# Complexity\n- Time complexity: O(nlogn)\n- Space complexity: O(n)\n\n# Code\n```c []\nstruct node {\n  double value;\n  int index;\n};\n\n#define get_parent(index) ((index - 1)>>1)\n#define get_left_child(index) ((index<<1) + 1)\n#define get_right_child(index) ((index<<1) + 2)\n\nvoid swap(struct node* a, struct node* b) {\n  struct node temp = *a;\n  *a = *b;\n  *b = temp;\n}\n\nvoid heap_sort(struct node* stack, int* size, int index) {\n  // moves up\n  int parent = get_parent(index);\n  while (index && stack[parent].value < stack[index].value) {\n    swap(stack + parent, stack + index);\n    index = parent;\n    parent = get_parent(index);\n  }\n  // moves down\n  int left = get_left_child(index);\n  int right = get_right_child(index);\n  while (left < *size && (stack[left].value > stack[index].value || stack[right].value > stack[index].value)) {\n    if (*size <= right) right = left;\n    if (stack[left].value > stack[right].value) right = left;\n    swap(stack + right, stack + index);\n    index = right;\n    left = get_left_child(index);\n    right = get_right_child(index);\n  }\n}\n\nvoid heap_insert(struct node* stack, int* size, struct node input) {\n  stack[*size] = input;\n  heap_sort(stack, size, *size);\n  ++(*size);\n}\n\nstruct node heap_pop(struct node* stack, int* size) {\n  struct node result = stack[0];\n  stack[0] = stack[*size - 1];\n  --(*size);\n  heap_sort(stack, size, 0);\n  return result;\n}\n\ndouble maxAverageRatio(int** classes, int classesSize, int* classesColSize, int extraStudents) {\n  struct node heap[classesSize];\n  int heap_size = 0;\n  for (int i = 0; i < classesSize; ++i) {\n    struct node current;\n    current.value = (double)(classes[i][0] + 1) / (classes[i][1] + 1);\n    current.value -= (double)(classes[i][0]) / (classes[i][1]);\n    current.index = i;\n    heap_insert(heap, &heap_size, current);\n  }\n  \n  while (extraStudents) {\n    struct node current = heap_pop(heap, &heap_size);\n    ++classes[current.index][0];\n    ++classes[current.index][1];\n    current.value = (double)(classes[current.index][0] + 1) / (classes[current.index][1] + 1);\n    current.value -= (double)(classes[current.index][0]) / (classes[current.index][1]);\n    heap_insert(heap, &heap_size, current);\n    --extraStudents;\n  }\n\n  double total = 0;\n  for (int i = 0; i < classesSize; ++i) total += (double)classes[i][0] / classes[i][1];\n  total /= classesSize;\n  return total;\n}\n```
['C']