JavaScript 최소 힙 연습: 동률 순서를 지키는 작업 스케줄러

한 파일로 실행하는 전체 정답

'use strict';

class MinHeap {
  constructor(compare = (a, b) => a - b) {
    if (typeof compare !== 'function') throw new TypeError('compare must be a function');
    this.compare = compare;
    this.data = [];
  }

  get size() {
    return this.data.length;
  }

  peek() {
    return this.data[0];
  }

  push(value) {
    if (value === undefined) throw new TypeError('undefined is reserved for an empty heap');
    let hole = this.data.length;
    this.data.push(value);
    while (hole > 0) {
      const parent = Math.floor((hole - 1) / 2);
      if (this.compare(this.data[parent], value) <= 0) break;
      this.data[hole] = this.data[parent];
      hole = parent;
    }
    this.data[hole] = value;
  }

  pop() {
    if (this.data.length === 0) return undefined;
    const minimum = this.data[0];
    const last = this.data.pop();
    if (this.data.length === 0) return minimum;

    let hole = 0;
    while (hole * 2 + 1 < this.data.length) {
      let child = hole * 2 + 1;
      const right = child + 1;
      if (right < this.data.length &&
          this.compare(this.data[right], this.data[child]) < 0) {
        child = right;
      }
      if (this.compare(last, this.data[child]) <= 0) break;
      this.data[hole] = this.data[child];
      hole = child;
    }
    this.data[hole] = last;
    return minimum;
  }
}

function solve({ tasks }) {
  const heap = new MinHeap((a, b) => a.priority - b.priority || a.order - b.order);
  tasks.forEach((task, order) => heap.push({ ...task, order }));
  const result = [];
  while (heap.size > 0) result.push(heap.pop().id);
  return result;
}

module.exports = { solve };

if (require.main === module) {
  const fs = require('node:fs');
  const input = JSON.parse(fs.readFileSync(0, 'utf8').replace(/^\uFEFF/, ''));
  process.stdout.write(JSON.stringify(solve(input)) + '\n');
}

정답 해설: 안정성을 비교 키로 바꿉니다

tasks.forEach의 인덱스는 입력 순서이며 모든 작업에서 다릅니다. (priority,order)를 사전식으로 비교하면 서로 다른 작업의 순서가 하나로 정해집니다. priority 차이가 0일 때만 order 차이를 사용하는 || 표현으로 이 계약을 구현합니다. 문제의 숫자 범위에서는 차이 연산도 안전한 정수입니다.

최소 힙의 부모는 항상 자식보다 앞선 작업입니다. 모든 작업을 push한 뒤 루트부터 pop하면 현재 남은 작업 중 가장 작은 비교 키가 차례로 나옵니다. 같은 우선순위라도 order가 작을수록 앞서므로 힙 내부 교체가 입력 순서를 바꿀 수 없습니다.

두 메일 요청은 ID가 같아도 order가 다르고 priority도 다릅니다. 결과에서 문자열만 보면 두 요청을 구분하지 못하지만 각각 한 번씩 실행된 것입니다. 반환 결과를 Set으로 만들면 요청 하나를 잃게 됩니다. 힙에 원본 객체를 그대로 넣고 order를 덧쓰지 않는 이유도 입력에 부수 효과를 만들지 않기 위해서입니다.

복잡도와 대안

작업 Q개를 하나씩 push하고 Q번 pop하므로 시간은 O(Q log(Q+1))입니다. 비교는 작은 정수 두 개만 사용해 O(1)입니다. 입력 문자열 총길이를 C라고 하면 입력·힙 객체·출력 배열을 포함한 공간은 O(Q+C)입니다. 문자열은 참조로 사용하므로 매 비교마다 ID 전체를 읽지 않습니다.

모든 작업이 처음부터 있고 전체 결과만 필요하면 (priority,입력 순번)으로 한 번 정렬하는 해법도 같은 점근 시간이며 더 짧습니다. 힙 구현의 학습 가치는 동적 우선순위 큐에 있습니다. 아래 코드에는 실행 중 우선순위 변경이나 임의 작업 취소 기능이 없으며 그런 기능을 있다고 가정하지 않습니다.

직접 확인할 경계

빈 tasks, 작업 하나, 모든 priority가 같은 목록, 음수 priority, 중복 ID를 확인하세요. 각 작업에 입력 인덱스를 붙여 배열 정렬한 결과를 기준으로 무작위 테스트하면 힙이 우선순위와 동률 계약을 동시에 지키는지 검증할 수 있습니다.