[Python/Java] Max Heap - Clean & Concise
Idea\n- How much profit we can get if we add one extraStudents to a particular class (pass, total)? This profit can be defined as: (pass+1)/(total+1) - pass/tot
**Idea**\n- How much profit we can get if we add one `extraStudents` to a particular class `(pass, total`)? This profit can be defined as: `(pass+1)/(total+1) - pass/total`.\n- For each student from `extraStudents`, we try to add to a class which will increase its profit maximum.\n- We can use `maxHeap` structure which can give us the class which has maximum profit after adding.\n\n**Complexity:**\n- Time: \n\t- Python: `O(M*logN + N)`, where `M` is `extraStudents` and `N` is number of classes.\n\t- Java: `O(M*logN + N*logN)`\n- Space: `O(N)`\n\n**Python**\n```python\nclass Solution(object):\n    def maxAverageRatio(self, classes, extraStudents):\n        def profit(a, b):\n            return (a + 1) / (b + 1) - a / b\n\n        maxHeap = []\n        for a, b in classes:\n            a, b = a * 1.0, b * 1.0  # Convert int to double\n            maxHeap.append((-profit(a, b), a, b))\n        heapq.heapify(maxHeap)  # Heapify maxHeap cost O(N)\n\n        for _ in range(extraStudents):\n            d, a, b = heapq.heappop(maxHeap)\n            heapq.heappush(maxHeap, (-profit(a + 1, b + 1), a + 1, b + 1))\n\n        return sum(a / b for d, a, b in maxHeap) / len(classes)\n```\n\n**Java**\n```java\nclass Solution {\n    public double maxAverageRatio(int[][] classes, int extraStudents) {\n        PriorityQueue<double[]> maxHeap = new PriorityQueue<>(Comparator.comparingDouble(o -> -o[0])); // Max heap compared by first value in decreasing order.\n        for (int[] c : classes) {\n            double a = c[0], b = c[1];\n            maxHeap.offer(new double[]{profit(a, b), a, b});\n        }\n        while (extraStudents-- > 0) {\n            double[] top = maxHeap.poll();\n            double a = top[1], b = top[2];\n            maxHeap.offer(new double[]{profit(a+1, b+1), a+1, b+1});\n        }\n        double ans = 0.0d;\n        while (!maxHeap.isEmpty()) {\n            double[] top = maxHeap.poll();\n            double a = top[1], b = top[2];\n            ans += a/b;\n        }\n        return ans / classes.length;\n    }\n    double profit(double a, double b) {\n        return (a + 1) / (b + 1) - a / b;\n    }\n}\n```\n
[]