class Solution {
 public:
  int largestInteger(int num) {
    const string s = to_string(num);
    int ans = 0;
    // maxHeap[0] := odd digits
    // maxHeap[1] := even digits
    vector<priority_queue<int>> maxHeap(2);

    for (const char c : s) {
      const int digit = c - '0';
      maxHeap[digit & 1].push(digit);
    }

    for (const char c : s) {
      const int i = c - '0' & 1;
      ans *= 10;
      ans += maxHeap[i].top(), maxHeap[i].pop();
    }

    return ans;
  }
};

class Solution {
  public int largestInteger(int num) {
    final String s = String.valueOf(num);
    int ans = 0;
    // maxHeap[0] := odd digits
    // maxHeap[1] := even digits
    Queue<Integer>[] maxHeap = new Queue[2];

    for (int i = 0; i < 2; ++i)
      maxHeap[i] = new PriorityQueue<>(Comparator.reverseOrder());

    for (final char c : s.toCharArray()) {
      final int digit = c - '0';
      maxHeap[digit & 1].offer(digit);
    }

    for (final char c : s.toCharArray()) {
      final int i = c - '0' & 1;
      ans = (ans * 10 + maxHeap[i].poll());
    }

    return ans;
  }
}

class Solution:
  def largestInteger(self, num: int) -> int:
    s = str(num)
    ans = 0
    # maxHeap[0] := odd digits
    # maxHeap[1] := even digits
    maxHeap = [[] for _ in range(2)]

    for c in s:
      digit = ord(c) - ord('0')
      heapq.heappush(maxHeap[digit & 1], -digit)

    for c in s:
      i = ord(c) - ord('0') & 1
      ans = (ans * 10 - heapq.heappop(maxHeap[i]))

    return ans