solver.js

import { PriorityQueue } from './collections.js';

export function findEncoding(frequencies) {
  const results = new Map();
  const partitioning = new PriorityQueue();
  for (const [meaning, frequency] of frequencies) {
    results.set(meaning, '');
    partitioning.insert(new Set([meaning]), frequency);
  }
  while (partitioning.size > 1) {
    const [firstMeaningSet, firstFrequency] = partitioning.remove();
    const [secondMeaningSet, secondFrequency] = partitioning.remove();
    for (const meaning of firstMeaningSet) {
      results.set(meaning, `0${results.get(meaning)}`);
    }
    for (const meaning of secondMeaningSet) {
      results.set(meaning, `1${results.get(meaning)}`);
    }
    partitioning.insert(
      new Set([...firstMeaningSet, ...secondMeaningSet]),
      firstFrequency + secondFrequency,
    );
  }
  return results;
}