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

'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;
}

import heapq
def solve(input):
    heap = [(t['priority'],i,t['id']) for i,t in enumerate(input['tasks'])]
    heapq.heapify(heap)
    return [heapq.heappop(heap)[2] for _ in range(len(heap))]

import java.util.*;
class Solution {
    public String[] solve(String[] ids, int[] priorities) {
        PriorityQueue < Integer > q = new PriorityQueue < >((a, b)->
            priorities[a] != priorities[b]
                ? Integer.compare(priorities[a], priorities[b])
                : Integer.compare(a, b)
        );
        for (int i = 0; i < ids.length; i++) q.add(i);
        String[] out = new String[ids.length];
        for (int i = 0; i < out.length; i++) out[i] = ids[q.remove()];
        return out;
    }
}

#include <string>
#include <vector>
#include <queue>
std::vector < std::string > solve(const std::vector < std::string > & ids, const std::vector < int > & priorities) {
    auto later = [&](int a, int b) {
        return priorities[a] != priorities[b] ? priorities[a] > priorities[b] : a > b;
    };
    std::priority_queue < int, std::vector < int >, decltype(later) > q(later);
    for (int i = 0; i <(int) ids.size(); i++) q.push(i);
    std::vector < std::string > out;
    while (! q.empty()) {
        out.push_back(ids[q.top()]);
        q.pop();
    }
    return out;
}

using System.Collections.Generic;
public class Solution {
    static bool Before(int a, int b, int[] p) {
        return p[a] < p[b] ||(p[a] == p[b] && a < b);
    }
    public string[] Solve(string[] ids, int[] priorities) {
        var heap = new List < int >();
        for (int i = 0; i < ids.Length; i++) {
            int k = heap.Count;
            heap.Add(i);
            while (k > 0) {
                int parent =(k - 1) / 2;
                if (! Before(heap[k], heap[parent], priorities)) break;
                int t = heap[k];
                heap[k] = heap[parent];
                heap[parent] = t;
                k = parent;
            }
        }
        var result = new List < string >();
        while (heap.Count > 0) {
            result.Add(ids[heap[0]]);
            int last = heap[heap.Count - 1];
            heap.RemoveAt(heap.Count - 1);
            if (heap.Count == 0) break;
            heap[0] = last;
            int k = 0;
            while (k * 2 + 1 < heap.Count) {
                int child = k * 2 + 1;
                if (child + 1 < heap.Count && Before(heap[child + 1], heap[child], priorities)) child++;
                if (! Before(heap[child], heap[k], priorities)) break;
                int t = heap[k];
                heap[k] = heap[child];
                heap[child] = t;
                k = child;
            }
        }
        return result.ToArray();
    }
}