Algorithms · 31
The greedy method and priority queues
Take what looks best at each step, and use a queue that hands out the smallest value right away.
The greedy method takes whatever looks best right now at every step.
A priority queue hands out the smallest (or largest) value first, whatever order the values went in.
The example below joins 5 piles of cards, two at a time, into one.
Each join costs as much effort as the two piles have cards in total; it always joins the two smallest piles, prints the effort of each join, and prints the sum of them all at the end.
import heapq n = int(input())piles = list(map(int, input().split()))heapq.heapify(piles) # 가장 작은 값이 언제나 맨 앞(piles[0])에 오게 한다 total = 0while len(piles) > 1: a = heapq.heappop(piles) # 가장 작은 두 묶음을 꺼낸다 b = heapq.heappop(piles) cost = a + b print(cost) total += cost heapq.heappush(piles, cost) # 합친 묶음을 다시 넣는다print(total)// 내장 우선순위 큐가 없다. 이만한 크기에서는 가장 작은 값을 직접 찾아 꺼내도 된다function popMin(list) { let at = 0; for (let i = 1; i < list.length; i++) if (list[i] < list[at]) at = i; return list.splice(at, 1)[0];} const t = require("fs").readFileSync(0, "utf8").trim().split(/\s+/).map(Number);const n = t[0];const piles = t.slice(1, 1 + n); let total = 0;while (piles.length > 1) { const a = popMin(piles); // 가장 작은 두 묶음을 꺼낸다 const b = popMin(piles); const cost = a + b; console.log(cost); total += cost; piles.push(cost); // 합친 묶음을 다시 넣는다}console.log(total);import { readFileSync } from "node:fs"; // 내장 우선순위 큐가 없다. 이만한 크기에서는 가장 작은 값을 직접 찾아 꺼내도 된다function popMin(list: number[]): number { let at = 0; for (let i = 1; i < list.length; i++) if (list[i] < list[at]) at = i; return list.splice(at, 1)[0];} const t: number[] = readFileSync(0, "utf8").trim().split(/\s+/).map(Number);const n: number = t[0];const piles: number[] = t.slice(1, 1 + n); let total = 0;while (piles.length > 1) { const a = popMin(piles); // 가장 작은 두 묶음을 꺼낸다 const b = popMin(piles); const cost = a + b; console.log(cost); total += cost; piles.push(cost); // 합친 묶음을 다시 넣는다}console.log(total);import java.util.PriorityQueue;import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); int n = in.nextInt(); PriorityQueue<Integer> piles = new PriorityQueue<>(); // 꺼내면 언제나 가장 작은 값이 나온다 for (int i = 0; i < n; i++) piles.add(in.nextInt()); int total = 0; while (piles.size() > 1) { int a = piles.poll(); // 가장 작은 두 묶음을 꺼낸다 int b = piles.poll(); int cost = a + b; System.out.println(cost); total += cost; piles.add(cost); // 합친 묶음을 다시 넣는다 } System.out.println(total); }}using System;using System.Collections.Generic; class Program{ static void Main() { int n = int.Parse(Console.ReadLine()); // (값, 우선순위) 짝으로 넣고, 우선순위가 가장 작은 것부터 나온다 PriorityQueue<int, int> piles = new PriorityQueue<int, int>(); foreach (string w in Console.ReadLine().Split()) piles.Enqueue(int.Parse(w), int.Parse(w)); int total = 0; while (piles.Count > 1) { int a = piles.Dequeue(); // 가장 작은 두 묶음을 꺼낸다 int b = piles.Dequeue(); int cost = a + b; Console.WriteLine(cost); total += cost; piles.Enqueue(cost, cost); // 합친 묶음을 다시 넣는다 } Console.WriteLine(total); }}#include <functional>#include <iostream>#include <queue>#include <vector> int main() { int n; std::cin >> n; // std::greater를 줘야 가장 작은 값이 먼저 나온다(기본은 가장 큰 값) std::priority_queue<int, std::vector<int>, std::greater<int>> piles; for (int i = 0; i < n; i++) { int x; std::cin >> x; piles.push(x); } int total = 0; while (piles.size() > 1) { int a = piles.top(); // 가장 작은 두 묶음을 꺼낸다 piles.pop(); int b = piles.top(); piles.pop(); int cost = a + b; std::cout << cost << '\n'; total += cost; piles.push(cost); // 합친 묶음을 다시 넣는다 } std::cout << total << '\n';}#include <stdio.h> int piles[1000];int count; // 내장 우선순위 큐가 없다. 이만한 크기에서는 가장 작은 값을 직접 찾아 꺼내도 된다int popMin(void) { int at = 0; for (int i = 1; i < count; i++) if (piles[i] < piles[at]) at = i; int v = piles[at]; piles[at] = piles[--count]; // 빈자리는 맨 끝 값으로 메운다 return v;} int main(void) { int n; scanf("%d", &n); for (int i = 0; i < n; i++) scanf("%d", &piles[i]); count = n; int total = 0; while (count > 1) { int a = popMin(); // 가장 작은 두 묶음을 꺼낸다 int b = popMin(); int cost = a + b; printf("%d\n", cost); total += cost; piles[count++] = cost; // 합친 묶음을 다시 넣는다 } printf("%d\n", total); return 0;}// 내장 우선순위 큐가 없다. 이만한 크기에서는 가장 작은 값을 직접 찾아 꺼내도 된다popMin(list){ at = 0; for (i = 1; i < list.Count; i++) { if (list[i] < list[at]) { at = i; } } v = list[at]; list.RemoveAt(at); return v;} n = Console.ReadLine().ToNumber();piles = Console.ReadNumbers(); total = 0;while (piles.Count > 1){ a = popMin(piles); // 가장 작은 두 묶음을 꺼낸다 b = popMin(piles); cost = a + b; Console.WriteLine(cost); total += cost; piles.Add(cost); // 합친 묶음을 다시 넣는다}Console.WriteLine(total);5 4 3 2 6 1
3 6 10 16 35
Key points
- The greedy method does not look ahead: it takes the best thing right now.
In the example that is the two smallest piles.
A pile joined early gets added again in later joins, so joining small ones first keeps the numbers that are added many times small. - Greedy is not right for every problem.
Making 6 from coins of 4, 3 and 1, taking the biggest coin first gives 4 + 1 + 1, 3 coins, while 3 + 3 needs only 2.
With coins of 500, 100, 50 and 10, biggest first is right. - So before solving something greedily, compare it on small inputs with the answer from trying every possibility.
If they differ even once, the rule is wrong.
The example's rule matched on all 3,000 small inputs tried. - The example keeps taking out the two smallest values and putting their sum back in.
New values keep arriving, so sorting once at the start is not enough.
This is where a priority queue is used. - Inside, a priority queue keeps its values in a shape called a heap.
It only guarantees that the front value is the smallest and does not keep the rest sorted, so adding and removing never walk over everything. - JavaScript, TypeScript, C and Craykon have no built-in priority queue.
The example scans the list for the smallest value on every removal.
At this size that is fine.
How each language writes it
| Python | import heapq — turn a list into a heap with heapq.heapify(piles), then heappush(piles, x) and heappop(piles).It only gives the smallest first, so to take the largest first push -x and flip the sign back after popping |
|---|---|
| JavaScript | There is no built-in priority queue. Find the position of the smallest value and take it out with splice(at, 1) as in the example; with many values, write a heap yourself |
| TypeScript | Same as JavaScript |
| Java | PriorityQueue<Integer> — add(x), poll() (remove), peek() (look only).Smallest first; for largest first use new PriorityQueue<>(Comparator.reverseOrder()).poll() on an empty queue gives null |
| C# | PriorityQueue<int, int> — Enqueue(value, priority), Dequeue(), Peek().The smallest priority comes out first, so for largest first give -x as the priority.Dequeue() on an empty queue throws InvalidOperationException |
| C++ | std::priority_queue<int> in <queue> gives the largest first.For smallest first use std::priority_queue<int, std::vector<int>, std::greater<int>>.Look with top() and remove with pop() (pop() returns nothing) |
| C | There is no built-in priority queue. Find the smallest value in the array and take it out as in the example; with many values, write a heap yourself |
| Craykon | There is no built-in priority queue. Find the position of the smallest value and take it out with RemoveAt(at) as in the example.This ran with up to 5,000 piles, but at 10,000 it was stopped for taking too long. In that case, write a heap yourself |
Common mistakes
Using greedy on a problem where it does not work
const coins = [4, 3, 1];
let left = 6, count = 0;
for (const c of coins) {
count += Math.floor(left / c);
left %= c;
}
console.log(count);→ 3 — that is 4 + 1 + 1. With 3 + 3 it takes only 2
Check on small examples that the biggest-first rule is right.
A coin problem like this is solved with dynamic programming, filling a table with the answer for each amount.
Expecting std::priority_queue to give the smallest firstC++
std::priority_queue<int> piles;
for (int x : {4, 3, 2, 6, 1}) piles.push(x);
std::cout << piles.top() << '\n';→ 6 — by default the largest value comes first
For smallest first, make it std::priority_queue<int, std::vector<int>, std::greater<int>>.
Python's heapq and Java's PriorityQueue are the other way round: smallest first.
Calling heappop without heapifyPython
import heapq
piles = [4, 3, 2, 6, 1]
print(heapq.heappop(piles))→ 4 — not the smallest, 1, but the value that was at the front. There is no error either
Call heapq.heapify(piles) first, or start from an empty list and add each value with heappush.
How languages differ
Scanning a list to remove the smallest is only for small amounts of data.
Measured on this computer, JavaScript took well under a second for 10,000 piles but about 10 seconds for 100,000, while Python's
In a language with no priority queue, write a heap yourself when there are many values, as the solutions to the practice problems do.
Scanning a list to remove the smallest is only for small amounts of data.
Measured on this computer, JavaScript took well under a second for 10,000 piles but about 10 seconds for 100,000, while Python's
heapq finished 100,000 in under a second.In a language with no priority queue, write a heap yourself when there are many values, as the solutions to the practice problems do.