Class Notes: Priority Queue Applications
(Greedy Algorithms)
The true power of the Priority Queue is revealed when implementing Greedy Algorithms. In
a maximization problem, a Max-Heap allows us to repeatedly find and process the current
best (most "greedy") option in $\mathcal{O}(\log N)$ time.
IV. Application: Maximum Score From Removing
Stones (Max-Heap)
Problem: Given three piles of stones ($a, b, c$), find the maximum score by taking one
stone from the two largest piles in each turn. The game stops when fewer than two piles
remain.
1. Approach A: Greedy Simulation using Max-Heap
Concept: To maximize the score, we must ensure the game lasts as long as possible. The
game ends when only one pile (or zero) remains. By always choosing the two largest piles,
we minimize the imbalance between the piles, preventing any single pile from dominating
and ending the game prematurely.
1. Use a Max-Heap to store the current sizes of the three piles.
2. In a loop, while $\text{Heap Size} > 1$:
a. Extract the two largest piles: maximum = poll(), secondMaximum = poll().
b. Decrement both values and increment the score.
c. If the decremented values are still positive, add them back to the heap.
3. The final score is the maximum possible.
● Time Complexity: $\mathcal{O}(S \log 3) \approx \mathcal{O}(S)$, where $S$ is the
final score (number of turns). Since $S \le a+b+c$, it is $\mathcal{O}(a+b+c)$.
● Space Complexity: $\mathcal{O}(1)$ (since the heap size is constant, $K=3$).
Java
class Solution {
public int maximumScore(int a, int b, int c) {
// Max Heap: Custom comparator (y - x) ensures largest element is the root
PriorityQueue<Integer> pq = new PriorityQueue<>((x, y) -> (y - x));
[Link](a);
[Link](b);
[Link](c);
int score = 0;
while([Link]() > 1) {
// Get the two largest piles
int maximum = [Link]();
int secondMaximum = [Link]();
score++;
maximum--;
secondMaximum--;
// Add back if they still have stones
if(maximum > 0) {
[Link](maximum);
}
if(secondMaximum > 0) {
[Link](secondMaximum);
}
}
return score;
}
}
2. Approach B: Mathematical Optimization
Concept: A simpler, non-simulation approach based on the relationship between the piles.
Let $A \le B \le C$ be the sorted pile sizes.
1. Case 1: Large Imbalance ($C \ge A + B$): The largest pile ($C$) is so big that it
can absorb all stones from $A$ and $B$. Every move will involve $C$. The game
stops as soon as $A$ and $B$ are exhausted. The maximum score is simply $A +
B$.
2. Case 2: Balanced ($C < A + B$): All stones can be removed roughly equally. The
score is $C$ (moves involving $C$ and the smaller two) plus the remaining moves,
which remove the final balance. The total stones are $A+B+C$. The largest pile $C$
forces $A+B-C$ stones to be removed from the smaller piles before $C$ becomes
the same size as the sum of the remaining two. The final score is $\text{Total Stones}
/ 2$. This simplifies to $C + ((A + B) - C) / 2$.
Java
class Solution {
public int maximumScore(int a, int b, int c) {
int [] arr = new int[]{a, b, c};
[Link](arr);
int A = arr[0]; // Smallest
int B = arr[1];
int C = arr[2]; // Largest
if(C >= A + B) {
// Case 1: Max pile dominates. Score = A + B (total moves before A and B empty).
return A + B;
} else {
// Case 2: Balanced. Score = Total Stones / 2.
// Integer division handles the final turn correctly.
return (A + B + C) / 2;
}
}
}
V. Application: Maximize Average Pass Ratio (Greedy
on Marginal Gain)
Problem: Given class pass/total ratios and $K$ extraStudents, assign each student to
maximize the average pass ratio across all classes.
Greedy Strategy: At each step, we must assign one student to the class that yields the
maximum marginal gain (the biggest increase in pass ratio) for that single student.
Implementation using Max-Heap
1. Define Marginal Gain: For a class with $\frac{p}{t}$ (pass/total), adding one student
yields a new ratio of $\frac{p+1}{t+1}$. The marginal gain is:
$$\text{Gain} = \frac{p+1}{t+1} - \frac{p}{t}$$
2. Max-Heap Structure: We use a Max-Heap that prioritizes classes based on their
current Gain. We store the class data as an array: [pass, total].
3. Simulation:
a. Initialize the heap with all classes.
b. Iterate $K$ times (for each extraStudent):
i. Poll the class with the maximum current Gain.
ii. Update its statistics: $p \to p+1$, $t \to t+1$.
iii. Insert the updated class back into the heap (its new marginal gain is calculated for
re-prioritization).
4. Final Calculation: After all students are assigned, sum the final pass ratios
($\frac{p}{t}$) and divide by the total number of classes.
● Time Complexity: $\mathcal{O}(N \log N + K \log N)$. $\mathcal{O}(N \log N)$ to
build the heap, and $K$ steps of $\mathcal{O}(\log N)$ for heap operations.
● Space Complexity: $\mathcal{O}(N)$ (to store $N$ classes in the heap).
Java
class Solution {
// Calculates the marginal gain for adding one student to class (a/b)
public double gain(int a, int b) {
return ((double) (a + 1) / (b + 1)) - ((double) (a) / b);
}
public double maxAverageRatio(int[][] classes, int extraStudents) {
// Max Heap: Comparator prioritizes the class with the largest potential 'gain'
// Note: The comparison logic (b-a) is flipped here because [Link] returns a
positive value
// if b > a, which means we want b (higher gain) to come first.
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) ->
([Link](gain(b[0], b[1]), gain(a[0], a[1]))));
int totalClasses = [Link];
// 1. Initialize heap
for(int i = 0; i < totalClasses; i++) {
[Link](new int[]{classes[i][0], classes[i][1]});
}
// 2. Perform K greedy assignments
while(extraStudents > 0) {
extraStudents--;
int[] top = [Link]();
top[0]++; // pass++
top[1]++; // total++
[Link](top); // Re-add with new stats and new gain
}
// 3. Calculate final average ratio
double totalRatio = 0.0;
while(![Link]()) {
int[] top = [Link]();
totalRatio += ((double)top[0] / top[1]);
}
return totalRatio / totalClasses;
}
}