✨Max Heap Explained Simply 🔑 |🔄 Beginner-Friendly 🔝 | Achieves 100% Success 🎯🔥
Intuition 🤔✨We want to maximize the average pass ratio 🤓. To do this:
1️⃣ Focus on the class that benefits the most 📈 when we add a student.
2️⃣ Repeat this for
# Intuition \uD83E\uDD14\u2728\nWe want to maximize the average pass ratio \uD83E\uDD13. To do this:\n1\uFE0F\u20E3 Focus on the class that benefits the most \uD83D\uDCC8 when we add a student.\n2\uFE0F\u20E3 Repeat this for every extraStudent \uD83D\uDC69\u200D\uD83C\uDF93\uD83D\uDC68\u200D\uD83C\uDF93.\n3\uFE0F\u20E3 The idea is to greedily improve the ratio of the most impactful class each time \uD83D\uDCA1.\n\n---\n\n# Approach \uD83D\uDEE0\uFE0F\uD83D\uDE80\n1\uFE0F\u20E3 Calculate Benefit: For each class, compute the increase in pass ratio if one student is added \uD83D\uDCCA.\n2\uFE0F\u20E3 Use a Max Heap \uD83C\uDFD4\uFE0F: Push all classes into a heap based on their benefit, so the class with the highest potential improvement is on top.\n3\uFE0F\u20E3 Add Students:    \n\n    While extraStudents > 0 \uD83D\uDC69\u200D\uD83C\uDF93:\n\n- Remove the top class from the heap \uD83D\uDC46.\n- Add one student to it \uD83E\uDDD1\u200D\uD83C\uDFEB.\n- Recompute its benefit and push it back into the heap \uD83D\uDD04.\n\n4\uFE0F\u20E3 Compute Final Average: After distributing all students, sum up the final ratios of all classes and divide by the total number of classes \uD83E\uDDEE.\n\n---\n\n# Complexity \u23F1\uFE0F\uD83D\uDCBE\n## Time: \n- *$$O(nlogn)$$* to build the heap initially. \n- *$$O(klogn)$$* for processing k students.\n- Total: *$$O((n+k)logn)$$* \uD83D\uDE80.\n## Space: *$$O(n)$$* for the heap storage \uD83D\uDDC2\uFE0F.\n\n---\n\n# Code\n```cpp []\nclass Solution {\npublic:\n    double maxAverageRatio(vector<vector<int>>& classes, int extraStudents) { \n        priority_queue<tuple<double, int, int>> maxHeap;\n\n        for(vector<int> cls: classes) {\n            int pass = cls[0], total = cls[1];\n            double diff = (double) (pass + 1)/(total + 1) - (double) pass /total;\n            maxHeap.push({diff, pass, total});\n        }        \n\n        while(extraStudents > 0) {\n            auto [diff, pass, total] = maxHeap.top();\n            maxHeap.pop();\n\n            pass ++;\n            total++;\n            double change = (double) (pass + 1)/(total + 1) - (double) pass /total;\n\n            maxHeap.push({change, pass, total});\n            extraStudents--;\n        }\n\n        double ans = 0;\n        while(!maxHeap.empty()) {\n            auto [ratio, pass, total] = maxHeap.top();\n            ans += (double) pass/total;\n            maxHeap.pop();\n        }\n        return (double) ans / classes.size();\n    }\n};\n```\n```java []\nimport java.util.PriorityQueue;\n\nclass Solution {\n    public double maxAverageRatio(int[][] classes, int extraStudents) {\n        PriorityQueue<double[]> maxHeap = new PriorityQueue<>((a, b) -> Double.compare(b[0], a[0]));\n\n        for (int[] cls : classes) {\n            int pass = cls[0], total = cls[1];\n            double diff = (double) (pass + 1) / (total + 1) - (double) pass / total;\n            maxHeap.offer(new double[]{diff, pass, total});\n        }\n\n        while (extraStudents > 0) {\n            double[] top = maxHeap.poll();\n            double diff = top[0];\n            int pass = (int) top[1];\n            int total = (int) top[2];\n            \n            pass++;\n            total++;\n            diff = (double) (pass + 1) / (total + 1) - (double) pass / total;\n\n            maxHeap.offer(new double[]{diff, pass, total});\n            extraStudents--;\n        }\n\n        double ans = 0;\n        while (!maxHeap.isEmpty()) {\n            double[] top = maxHeap.poll();\n            ans += (double) top[1] / top[2];\n        }\n        return ans / classes.length;\n    }\n}\n\n```\n```python []\nimport heapq\n\nclass Solution:\n    def maxAverageRatio(self, classes, extraStudents):\n        maxHeap = []\n        for passed, total in classes:\n            diff = (passed + 1) / (total + 1) - passed / total\n            heapq.heappush(maxHeap, (-diff, passed, total))\n\n        while extraStudents > 0:\n            diff, passed, total = heapq.heappop(maxHeap)\n            passed += 1\n            total += 1\n            diff = (passed + 1) / (total + 1) - passed / total\n            heapq.heappush(maxHeap, (-diff, passed, total))\n            extraStudents -= 1\n\n        return sum(passed / total for _, passed, total in maxHeap) / len(classes)\n\n```\n```javascript []\nvar maxAverageRatio = function(classes, extraStudents) {\n    const maxHeap = new MaxPriorityQueue({ priority: x => x.diff });\n\n    for (let [pass, total] of classes) {\n        const diff = (pass + 1) / (total + 1) - pass / total;\n        maxHeap.enqueue({ diff, pass, total });\n    }\n\n    while (extraStudents > 0) {\n        const { pass, total } = maxHeap.dequeue();\n        const newPass = pass + 1;\n        const newTotal = total + 1;\n        const newDiff = (newPass + 1) / (newTotal + 1) - newPass / newTotal;\n        maxHeap.enqueue({ diff: newDiff, pass: newPass, total: newTotal });\n        extraStudents--;\n    }\n\n    let sum = 0;\n    while (!maxHeap.isEmpty()) {\n        const { pass, total } = maxHeap.dequeue();\n        sum += pass / total;\n    }\n    return sum / classes.length;\n};\n\n```\n```ruby []\nrequire \'priority_queue\'\n\ndef max_average_ratio(classes, extra_students)\n  max_heap = PriorityQueue.new\n  \n  classes.each do |pass, total|\n    diff = (pass + 1).to_f / (total + 1) - pass.to_f / total\n    max_heap.push([pass, total], -diff)\n  end\n\n  while extra_students > 0\n    pass, total = max_heap.pop\n    pass += 1\n    total += 1\n    diff = (pass + 1).to_f / (total + 1) - pass.to_f / total\n    max_heap.push([pass, total], -diff)\n    extra_students -= 1\n  end\n\n  sum = 0.0\n  until max_heap.empty?\n    pass, total = max_heap.pop\n    sum += pass.to_f / total\n  end\n  sum / classes.size\nend\n\n```\n```rust []\nuse std::collections::BinaryHeap;\n\nimpl Solution {\n    pub fn max_average_ratio(classes: Vec<Vec<i32>>, extra_students: i32) -> f64 {\n        let mut max_heap = BinaryHeap::new();\n\n        for cls in classes {\n            let (pass, total) = (cls[0], cls[1]);\n            let diff = (pass + 1) as f64 / (total + 1) as f64 - pass as f64 / total as f64;\n            max_heap.push((diff, pass, total));\n        }\n\n        let mut extra = extra_students;\n        while extra > 0 {\n            let (diff, mut pass, mut total) = max_heap.pop().unwrap();\n            pass += 1;\n            total += 1;\n            let new_diff = (pass + 1) as f64 / (total + 1) as f64 - pass as f64 / total as f64;\n            max_heap.push((new_diff, pass, total));\n            extra -= 1;\n        }\n\n        let mut sum = 0.0;\n        while let Some((_, pass, total)) = max_heap.pop() {\n            sum += pass as f64 / total as f64;\n        }\n        sum / classes.len() as f64\n    }\n}\n\n```\n```go []\nimport (\n    "container/heap"\n)\n\nfunc maxAverageRatio(classes [][]int, extraStudents int) float64 {\n    h := &MaxHeap{}\n    heap.Init(h)\n\n    for _, class := range classes {\n        pass, total := class[0], class[1]\n        diff := float64(pass+1)/float64(total+1) - float64(pass)/float64(total)\n        heap.Push(h, []float64{diff, float64(pass), float64(total)})\n    }\n\n    for extraStudents > 0 {\n        top := heap.Pop(h).([]float64)\n        pass, total := top[1]+1, top[2]+1\n        diff := float64(pass+1)/float64(total+1) - float64(pass)/float64(total)\n        heap.Push(h, []float64{diff, pass, total})\n        extraStudents--\n    }\n\n    var sum float64\n    for h.Len() > 0 {\n        top := heap.Pop(h).([]float64)\n        sum += top[1] / top[2]\n    }\n    return sum / float64(len(classes))\n}\n\ntype MaxHeap [][]float64\n\nfunc (h MaxHeap) Len() int            { return len(h) }\nfunc (h MaxHeap) Less(i, j int) bool  { return h[i][0] > h[j][0] }\nfunc (h MaxHeap) Swap(i, j int)       { h[i], h[j] = h[j], h[i] }\nfunc (h *MaxHeap) Push(x interface{}) { *h = append(*h, x.([]float64)) }\nfunc (h *MaxHeap) Pop() interface{} {\n    old := *h\n    n := len(old)\n    x := old[n-1]\n    *h = old[:n-1]\n    return x\n}\n\n```\n```c# []\nusing System;\nusing System.Collections.Generic;\n\npublic class Solution {\n    public double MaxAverageRatio(int[][] classes, int extraStudents) {\n        var maxHeap = new PriorityQueue<(double diff, int pass, int total), double>();\n        \n        foreach (var cls in classes) {\n            int pass = cls[0], total = cls[1];\n            double diff = (double)(pass + 1) / (total + 1) - (double)pass / total;\n            maxHeap.Enqueue((diff, pass, total), -diff);\n        }\n\n        while (extraStudents > 0) {\n            var (diff, pass, total) = maxHeap.Dequeue();\n            pass++;\n            total++;\n            diff = (double)(pass + 1) / (total + 1) - (double)pass / total;\n            maxHeap.Enqueue((diff, pass, total), -diff);\n            extraStudents--;\n        }\n\n        double sum = 0;\n        while (maxHeap.Count > 0) {\n            var (_, pass, total) = maxHeap.Dequeue();\n            sum += (double)pass / total;\n        }\n        return sum / classes.Length;\n    }\n}\n\n```\n```typescript []\nfunction maxAverageRatio(classes: number[][], extraStudents: number): number {\n    const maxHeap = new MaxPriorityQueue<{ diff: number, pass: number, total: number }>({ priority: x => x.diff });\n\n    for (const [pass, total] of classes) {\n        const diff = (pass + 1) / (total + 1) - pass / total;\n        maxHeap.enqueue({ diff, pass, total });\n    }\n\n    while (extraStudents > 0) {\n        const { pass, total } = maxHeap.dequeue();\n        const newPass = pass + 1;\n        const newTotal = total + 1;\n        const newDiff = (newPass + 1) / (newTotal + 1) - newPass / newTotal;\n        maxHeap.enqueue({ diff: newDiff, pass: newPass, total: newTotal });\n        extraStudents--;\n    }\n\n    let sum = 0;\n    while (!maxHeap.isEmpty()) {\n        const { pass, total } = maxHeap.dequeue();\n        sum += pass / total;\n    }\n    return sum / classes.length;\n}\n\n```\n```dart []\nimport \'dart:collection\';\n\nclass Solution {\n  double maxAverageRatio(List<List<int>> classes, int extraStudents) {\n    var maxHeap = PriorityQueue<List<double>>((a, b) => b[0].compareTo(a[0]));\n\n    for (var cls in classes) {\n      int pass = cls[0], total = cls[1];\n      double diff = (pass + 1) / (total + 1) - pass / total;\n      maxHeap.add([diff, pass.toDouble(), total.toDouble()]);\n    }\n\n    while (extraStudents > 0) {\n      var top = maxHeap.removeFirst();\n      var pass = top[1] + 1;\n      var total = top[2] + 1;\n      var diff = (pass + 1) / (total + 1) - pass / total;\n      maxHeap.add([diff, pass, total]);\n      extraStudents--;\n    }\n\n    double sum = 0;\n    while (maxHeap.isNotEmpty) {\n      var top = maxHeap.removeFirst();\n      sum += top[1] / top[2];\n    }\n    return sum / classes.length;\n  }\n}\n\n```\n```swift []\nimport Foundation\n\nfunc maxAverageRatio(_ classes: [[Int]], _ extraStudents: Int) -> Double {\n    var maxHeap = Heap { (a: (Double, Int, Int), b: (Double, Int, Int)) in a.0 > b.0 }\n\n    for cls in classes {\n        let pass = cls[0], total = cls[1]\n        let diff = Double(pass + 1) / Double(total + 1) - Double(pass) / Double(total)\n        maxHeap.insert((diff, pass, total))\n    }\n\n    var extra = extraStudents\n    while extra > 0 {\n        let (diff, pass, total) = maxHeap.remove()!\n        let newPass = pass + 1, newTotal = total + 1\n        let newDiff = Double(newPass + 1) / Double(newTotal + 1) - Double(newPass) / Double(newTotal)\n        maxHeap.insert((newDiff, newPass, newTotal))\n        extra -= 1\n    }\n\n    var sum = 0.0\n    while let (_, pass, total) = maxHeap.remove() {\n        sum += Double(pass) / Double(total)\n    }\n    return sum / Double(classes.count)\n}\n\nstruct Heap<T> {\n    var nodes = [T]()\n    let comparator: (T, T) -> Bool\n\n    init(comparator: @escaping (T, T) -> Bool) {\n        self.comparator = comparator\n    }\n\n    mutating func insert(_ value: T) {\n        nodes.append(value)\n        siftUp(from: nodes.count - 1)\n    }\n\n    mutating func remove() -> T? {\n        guard !nodes.isEmpty else { return nil }\n        if nodes.count == 1 { return nodes.removeLast() }\n        let value = nodes[0]\n        nodes[0] = nodes.removeLast()\n        siftDown(from: 0)\n        return value\n    }\n\n    private mutating func siftUp(from index: Int) {\n        var child = index\n        var parent = (child - 1) / 2\n        while child > 0 && comparator(nodes[child], nodes[parent]) {\n            nodes.swapAt(child, parent)\n            child = parent\n            parent = (child - 1) / 2\n        }\n    }\n\n    private mutating func siftDown(from index: Int) {\n        var parent = index\n        while true {\n            let left = 2 * parent + 1, right = 2 * parent + 2\n            var candidate = parent\n            if left < nodes.count && comparator(nodes[left], nodes[candidate]) { candidate = left }\n            if right < nodes.count && comparator(nodes[right], nodes[candidate]) { candidate = right }\n            if candidate == parent { return }\n            nodes.swapAt(parent, candidate)\n            parent = candidate\n        }\n    }\n}\n\n```\n
['Swift', 'Heap (Priority Queue)', 'Python', 'C++', 'Java', 'Go', 'Rust', 'Ruby', 'C#', 'Dart']