const rearrangeBarcodes = (arr) => {
  const ans = [];

  // arr to hashmap
  const hash = {};
  arr.forEach((item) => {
    hash[item] = hash[item] ? ++hash[item] : 1;
  });

  // helper
  const swap = (arr, idx1, idx2) => {
    const temp = arr[idx1];
    arr[idx1] = arr[idx2];
    arr[idx2] = temp;
  };

  // hash to pq, heapify up
  const pq = [null];

  Object.entries(hash).forEach((item) => {
    const [value, freq] = item;
    pq.push({ value, freq });

    let childIdx = pq.length - 1;

    while (childIdx > 1) {
      let parentIdx = Math.floor(childIdx / 2);

      if (pq[parentIdx].freq < freq) {
        swap(pq, parentIdx, childIdx);
      }
      childIdx = parentIdx;
    }
  });

  const poll = (value) => {
    let idx = 1;

    if (pq[idx].value === value) {
      const left = pq[2];
      const right = pq[3];
      if (pq[2].freq !== 0) {
        idx = 2;
        if (right && right.freq !== 0) {
          idx = pq[2] > pq[3] ? 2 : 3;
        }
      }
    }

    let head = pq[idx];

    ans.push(head.value);
    head.freq--;

    while (idx * 2 < pq.length) {
      // heapify down
      const leftIdx = idx * 2;
      const rightIdx = idx * 2 + 1;

      let childMaxIdx = leftIdx;
      if (rightIdx < pq.length) {
        childMaxIdx = pq[leftIdx].freq > pq[rightIdx].freq ? leftIdx : rightIdx;
      }
      if (pq[idx].freq < pq[childMaxIdx].freq) {
        swap(pq, idx, childMaxIdx);
        if (idx === 0) {
          head = pq[idx];
        }
      }
      idx = childMaxIdx;
    }
    return head.value;
  };

  let recent = poll();
  while (pq[1].freq) {
    const last = poll(recent);
    recent = last;
  }

  return ans;
};