任务队列与中位数

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"));

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);    }}

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);    }}