Write a priority queue interface and a generic binary heap class that takes a way to compare and implements that interface. Do not use the priority queue built into the language.
Use that one heap class for both the task queue and the two integer heaps that find the median of the priorities.
The first line has the number of commands n, and the next n lines have one command each.
"add name p" puts a task named name with priority p into the queue. The same name may appear several times; they count as different tasks.
"next" takes the task with the largest priority out of the queue and prints "name p". If priorities are equal, the task added first comes out first. If the queue is empty, print -.
"median" prints the median of all priorities added with add so far. Priorities of tasks already taken out still count.
If an even number of priorities has been added, print the smaller of the two middle values. If nothing has been added yet, print -.
Input
1 ≤ n ≤ 100,000. name is 1 to 10 lowercase English letters. -2,000,000,000 ≤ p ≤ 2,000,000,000 (integer). There are at most 5,000 next and median commands in total.
Output
one line per next and median
Example 1 · stdin
9
add wash 3
add cook 5
add read 5
median
next
next
add nap -2
median
next
stdout
5
cook 5
read 5
3
wash 3
Example 2 · stdin
6
next
median
add big 2000000000
add low -2000000000
next
median
stdout
-
-
big 2000000000
-2000000000
main.py
Error List00F8 ↓ · ⇧F8 ↑
Input (stdin)
When you run, these lines are fed to input()/stdin in order (the program doesn't stop to ask).
$ Ready
Open this on a computer to write and run code. On mobile you can read the problem and the solutions.
In other languagesShow solutions by language · 3 languages
This problem takes only TypeScript, Java and C#, which have interfaces and generics (JS has neither interfaces nor type parameters, and Python can write Protocol and type parameters but does not check them at run time; C and Craykon have neither, and C++ templates look very different, so they are left out). One heap class is used for tasks (Task) and for integers by changing only T and the way to compare. The comparison is taken as a function type: Java Comparator<? super T>, C# Comparison<T>, TS (a: T, b: T) => boolean. Java cannot write BinaryHeap<int>, so it holds Integer; C# generics hold int without boxing. The built-in priority queues differ too. Java java.util.PriorityQueue and C# PriorityQueue<TElement, TPriority> (.NET 6) give the smallest first, and TS (JavaScript) has none at all. Iterating or printing a Java queue shows heap-array order, which is not sorted. Three traps: (1) comparing by subtraction like b - a overflows Java/C# int for 2e9 − (−2e9) and flips the sign; use Integer.compare / CompareTo (TS numbers are doubles and do not overflow). (2) A heap does not keep insertion order among equals. Neither built-in queue promises an order for equal priorities either, so giving the C# built-in queue only the priority mixes up tasks of equal priority. The insertion order must be part of the comparison. (3) In TS strict mode pop() returns T | undefined, which must be checked before use. Silencing the check with ! compiles, but taking from an empty queue throws TypeError (the Java solution signals with null, the C# solution with TryPop returning false). For the median, keep the smaller half in a heap with the largest on top and the larger half in a heap with the smallest on top; if the smaller half is kept equal in size or one larger, its top is the answer.
TypeScriptmain.ts · 87 lines
import { readFileSync } from "node:fs";// 우선순위 큐의 약속: 어떤 T든, "먼저 나올 것"을 정하는 비교 함수만 있으면 된다interface PriorityQueue<T> { push(item: T): void; pop(): T | undefined; // 비었으면 undefined peek(): T | undefined; size(): number;}// 이진 힙: before(a, b)가 참이면 a가 b보다 먼저 나온다class BinaryHeap<T> implements PriorityQueue<T> { private items: T[] = []; constructor(private before: (a: T, b: T) => boolean) {} push(item: T): void { const a = this.items; a.push(item); let i = a.length - 1; while (i > 0) { const parent = (i - 1) >> 1; if (!this.before(a[i], a[parent])) break; [a[i], a[parent]] = [a[parent], a[i]]; i = parent; } } pop(): T | undefined { const a = this.items; if (a.length === 0) return undefined; const top = a[0]; const last = a.pop() as T; if (a.length > 0) { a[0] = last; let i = 0; for (;;) { const l = 2 * i + 1, r = l + 1; let best = i; if (l < a.length && this.before(a[l], a[best])) best = l; if (r < a.length && this.before(a[r], a[best])) best = r; if (best === i) break; [a[i], a[best]] = [a[best], a[i]]; i = best; } } return top; } peek(): T | undefined { return this.items[0]; } size(): number { return this.items.length; }}interface Task { name: string; priority: number; order: number; // 넣은 차례: 우선순위가 같으면 먼저 넣은 것부터}// 같은 BinaryHeap을 T = Task, T = number로 쓴다const tasks = new BinaryHeap<Task>((a, b) => a.priority !== b.priority ? a.priority > b.priority : a.order < b.order);const low = new BinaryHeap<number>((a, b) => a > b); // 작은 절반, 가장 큰 것이 위const high = new BinaryHeap<number>((a, b) => a < b); // 큰 절반, 가장 작은 것이 위function addPriority(p: number): void { low.push(p); high.push(low.pop() as number); // 작은 절반의 가장 큰 것을 큰 절반으로 if (high.size() > low.size()) low.push(high.pop() as number);}const lines: string[] = readFileSync(0, "utf8").split("\n");const n: number = Number(lines[0]);const out: string[] = [];for (let i = 1; i <= n; i++) { const [op, name, p] = lines[i].trim().split(" "); if (op === "add") { tasks.push({ name, priority: Number(p), order: i }); addPriority(Number(p)); } else if (op === "next") { const t = tasks.pop(); out.push(t === undefined ? "-" : `${t.name} ${t.priority}`); } else { const m = low.peek(); out.push(m === undefined ? "-" : String(m)); }}console.log(out.join("\n"));
JavaMain.java · 102 lines
import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayList;import java.util.Comparator;import java.util.List;// 우선순위 큐의 약속: 어떤 T든, 비교 방법(Comparator)만 있으면 된다interface PriorityQueue<T> { void push(T item); T pop(); // 비었으면 null T peek(); // 비었으면 null int size();}// 이진 힙: order.compare(a, b) < 0 이면 a가 b보다 먼저 나온다class BinaryHeap<T> implements PriorityQueue<T> { private final List<T> items = new ArrayList<>(); private final Comparator<? super T> order; BinaryHeap(Comparator<? super T> order) { this.order = order; } private boolean before(int i, int j) { return order.compare(items.get(i), items.get(j)) < 0; } private void swap(int i, int j) { T tmp = items.get(i); items.set(i, items.get(j)); items.set(j, tmp); } public void push(T item) { items.add(item); int i = items.size() - 1; while (i > 0 && before(i, (i - 1) / 2)) { swap(i, (i - 1) / 2); i = (i - 1) / 2; } } public T pop() { if (items.isEmpty()) return null; T top = items.get(0); T last = items.remove(items.size() - 1); if (!items.isEmpty()) { items.set(0, last); int i = 0; while (true) { int l = 2 * i + 1, r = l + 1, best = i; if (l < items.size() && before(l, best)) best = l; if (r < items.size() && before(r, best)) best = r; if (best == i) break; swap(i, best); i = best; } } return top; } public T peek() { return items.isEmpty() ? null : items.get(0); } public int size() { return items.size(); }}record Task(String name, int priority, int order) {}public class Main { // 같은 BinaryHeap을 T = Task, T = Integer로 쓴다(List<int>처럼 int는 못 넣는다) static final PriorityQueue<Task> tasks = new BinaryHeap<>( Comparator.comparingInt(Task::priority).reversed().thenComparingInt(Task::order)); static final PriorityQueue<Integer> low = new BinaryHeap<>(Comparator.reverseOrder()); // 작은 절반, 가장 큰 것이 위 static final PriorityQueue<Integer> high = new BinaryHeap<>(Comparator.naturalOrder()); // 큰 절반, 가장 작은 것이 위 static void addPriority(int p) { low.push(p); high.push(low.pop()); // 작은 절반의 가장 큰 것을 큰 절반으로 if (high.size() > low.size()) low.push(high.pop()); } public static void main(String[] args) throws IOException { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(in.readLine().trim()); StringBuilder out = new StringBuilder(); for (int i = 1; i <= n; i++) { String[] p = in.readLine().trim().split(" "); switch (p[0]) { case "add" -> { int pri = Integer.parseInt(p[2]); tasks.push(new Task(p[1], pri, i)); addPriority(pri); } case "next" -> { Task t = tasks.pop(); out.append(t == null ? "-" : t.name() + " " + t.priority()).append('\n'); } default -> { Integer m = low.peek(); out.append(m == null ? "-" : m.toString()).append('\n'); } } } System.out.print(out); }}
C#Main.cs · 103 lines
using System;using System.Collections.Generic;using System.Text;// 우선순위 큐의 약속: 어떤 T든, 비교 방법(Comparison<T>)만 있으면 된다interface IPriorityQueue<T>{ void Push(T item); bool TryPop(out T item); // 비었으면 false bool TryPeek(out T item); int Count { get; }}// 이진 힙: order(a, b) < 0 이면 a가 b보다 먼저 나온다class BinaryHeap<T> : IPriorityQueue<T>{ private readonly List<T> items = new(); private readonly Comparison<T> order; public BinaryHeap(Comparison<T> order) { this.order = order; } private bool Before(int i, int j) => order(items[i], items[j]) < 0; private void Swap(int i, int j) => (items[i], items[j]) = (items[j], items[i]); public void Push(T item) { items.Add(item); int i = items.Count - 1; while (i > 0 && Before(i, (i - 1) / 2)) { Swap(i, (i - 1) / 2); i = (i - 1) / 2; } } public bool TryPop(out T item) { if (items.Count == 0) { item = default!; return false; } item = items[0]; items[0] = items[^1]; items.RemoveAt(items.Count - 1); int i = 0; while (true) { int l = 2 * i + 1, r = l + 1, best = i; if (l < items.Count && Before(l, best)) best = l; if (r < items.Count && Before(r, best)) best = r; if (best == i) break; Swap(i, best); i = best; } return true; } public bool TryPeek(out T item) { item = items.Count > 0 ? items[0] : default!; return items.Count > 0; } public int Count => items.Count;}record Task(string Name, int Priority, int Order);class Program{ // 같은 BinaryHeap을 T = Task, T = int로 쓴다(C# 제네릭은 int를 포장 없이 담는다) static readonly IPriorityQueue<Task> tasks = new BinaryHeap<Task>((a, b) => a.Priority != b.Priority ? b.Priority.CompareTo(a.Priority) : a.Order.CompareTo(b.Order)); static readonly IPriorityQueue<int> low = new BinaryHeap<int>((a, b) => b.CompareTo(a)); // 작은 절반, 가장 큰 것이 위 static readonly IPriorityQueue<int> high = new BinaryHeap<int>((a, b) => a.CompareTo(b)); // 큰 절반, 가장 작은 것이 위 static void AddPriority(int p) { low.Push(p); low.TryPop(out int top); high.Push(top); // 작은 절반의 가장 큰 것을 큰 절반으로 if (high.Count > low.Count && high.TryPop(out int small)) low.Push(small); } static void Main() { int n = int.Parse(Console.ReadLine()!.Trim()); var output = new StringBuilder(); for (int i = 1; i <= n; i++) { string[] p = Console.ReadLine()!.Trim().Split(' '); if (p[0] == "add") { int pri = int.Parse(p[2]); tasks.Push(new Task(p[1], pri, i)); AddPriority(pri); } else if (p[0] == "next") output.Append(tasks.TryPop(out var t) ? $"{t.Name} {t.Priority}" : "-").Append('\n'); else output.Append(low.TryPeek(out int m) ? m.ToString() : "-").Append('\n'); } Console.Write(output); }}