Largest Number After Digit Swaps by Parity

class Solution {
public:
    int largestInteger(int num) {
        string s = to_string(num);
        priority_queue<int> odd, even;
        for (char c : s) (c - '0') % 2 == 0 ? even.push(c - '0') : odd.push(c - '0');
        for (char& c : s) {
            int d = c - '0';
            if (d % 2 == 0) { c = '0' + even.top(); even.pop(); }
            else { c = '0' + odd.top(); odd.pop(); }
        }
        return stoi(s);
    }
};

import (
    "container/heap"
    "strconv"
)

type maxDigitHeap []int

func (h maxDigitHeap) Len() int            { return len(h) }
func (h maxDigitHeap) Less(i, j int) bool  { return h[i] > h[j] }
func (h maxDigitHeap) Swap(i, j int)       { h[i], h[j] = h[j], h[i] }
func (h *maxDigitHeap) Push(x interface{}) { *h = append(*h, x.(int)) }
func (h *maxDigitHeap) Pop() interface{} {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[:n-1]
    return x
}

func largestInteger(num int) int {
    s := []byte(strconv.Itoa(num))
    odd, even := &maxDigitHeap{}, &maxDigitHeap{}
    for _, c := range s {
        d := int(c - '0')
        if d%2 == 0 {
            heap.Push(even, d)
        } else {
            heap.Push(odd, d)
        }
    }
    for i, c := range s {
        d := int(c - '0')
        if d%2 == 0 {
            s[i] = byte('0' + heap.Pop(even).(int))
        } else {
            s[i] = byte('0' + heap.Pop(odd).(int))
        }
    }
    v, _ := strconv.Atoi(string(s))
    return v
}

import heapq

class Solution:
    def largestInteger(self, num: int) -> int:
        s = list(str(num))
        odd, even = [], []
        for c in s:
            d = int(c)
            # negate for max-heap
            if d % 2 == 0:
                heapq.heappush(even, -d)
            else:
                heapq.heappush(odd, -d)
        for i, c in enumerate(s):
            d = int(c)
            if d % 2 == 0:
                s[i] = str(-heapq.heappop(even))
            else:
                s[i] = str(-heapq.heappop(odd))
        return int("".join(s))

class MaxHeap {
    constructor() { this.h = []; }
    size() { return this.h.length; }
    push(v) {
        this.h.push(v);
        let i = this.h.length - 1;
        while (i > 0) {
            const p = (i - 1) >> 1;
            if (this.h[p] < this.h[i]) { [this.h[p], this.h[i]] = [this.h[i], this.h[p]]; i = p; }
            else break;
        }
    }
    pop() {
        const top = this.h[0];
        const last = this.h.pop();
        if (this.h.length) {
            this.h[0] = last;
            let i = 0, n = this.h.length;
            while (true) {
                const l = 2 * i + 1, r = 2 * i + 2;
                let best = i;
                if (l < n && this.h[l] > this.h[best]) best = l;
                if (r < n && this.h[r] > this.h[best]) best = r;
                if (best === i) break;
                [this.h[best], this.h[i]] = [this.h[i], this.h[best]];
                i = best;
            }
        }
        return top;
    }
}

function largestInteger(num) {
    const s = String(num).split('');
    const odd = new MaxHeap(), even = new MaxHeap();
    for (const c of s) {
        const d = +c;
        if (d % 2 === 0) even.push(d);
        else odd.push(d);
    }
    for (let i = 0; i < s.length; i++) {
        const d = +s[i];
        s[i] = String(d % 2 === 0 ? even.pop() : odd.pop());
    }
    return parseInt(s.join(''), 10);
}

class Solution {
    public int largestInteger(int num) {
        char[] s = String.valueOf(num).toCharArray();
        PriorityQueue<Integer> odd = new PriorityQueue<>(Comparator.reverseOrder());
        PriorityQueue<Integer> even = new PriorityQueue<>(Comparator.reverseOrder());
        for (char c : s) {
            int d = c - '0';
            if (d % 2 == 0) even.offer(d);
            else odd.offer(d);
        }
        for (int i = 0; i < s.length; i++) {
            int d = s[i] - '0';
            if (d % 2 == 0) s[i] = (char) ('0' + even.poll());
            else s[i] = (char) ('0' + odd.poll());
        }
        return Integer.parseInt(new String(s));
    }
}

class MaxHeap {
    private h: number[] = [];
    size(): number { return this.h.length; }
    push(v: number): void {
        this.h.push(v);
        let i = this.h.length - 1;
        while (i > 0) {
            const p = (i - 1) >> 1;
            if (this.h[p] < this.h[i]) { [this.h[p], this.h[i]] = [this.h[i], this.h[p]]; i = p; }
            else break;
        }
    }
    pop(): number {
        const top = this.h[0];
        const last = this.h.pop() as number;
        if (this.h.length) {
            this.h[0] = last;
            let i = 0;
            const n = this.h.length;
            while (true) {
                const l = 2 * i + 1, r = 2 * i + 2;
                let best = i;
                if (l < n && this.h[l] > this.h[best]) best = l;
                if (r < n && this.h[r] > this.h[best]) best = r;
                if (best === i) break;
                [this.h[best], this.h[i]] = [this.h[i], this.h[best]];
                i = best;
            }
        }
        return top;
    }
}

function largestInteger(num: number): number {
    const s = String(num).split('');
    const odd = new MaxHeap(), even = new MaxHeap();
    for (const c of s) {
        const d = +c;
        if (d % 2 === 0) even.push(d);
        else odd.push(d);
    }
    for (let i = 0; i < s.length; i++) {
        const d = +s[i];
        s[i] = String(d % 2 === 0 ? even.pop() : odd.pop());
    }
    return parseInt(s.join(''), 10);
}