具有 O(1) Get-Min、Delete-Min 和 Merge 操作的优先级队列

Question

我想知道是否有一种方法可以构造一个支持恒定时间get-min、delete-min 和merge 操作的优先级队列结构。我不关心插入的时间复杂度，也不需要支持减键操作。我在（错误的）伪代码中的用例：

func periodical(current_state) {
    // always_executed_jobs is a priority queue
    queue = always_executed_jobs;
    // other_jobs is an array of priority queues;
    // current_state is an index to the array, so
    // sometimes_executed_jobs is another priority queue
    sometimes_executed_jobs = other_jobs[current_state];
    queue.merge(sometimes_executed_jobs);
    while (!queue.empty()) {
        job = get_min(queue);
        execute(job);
        delete_min(queue);
    }
}

我考虑过 splay 树（特别是 https://cs.stackexchange.com/questions/524/does-there-exist-a-priority-queue-with-o1-extracts）和 Fibonacci 堆，但它们似乎不能满足这些要求。

Answer 1

如果只能比较优先级，这是不可能的。问题是恒定时间 merge 可用于在恒定时间内模拟 insert，由于 delete-min 也是恒定时间，因此违反了已知的排序下限。

具有 O(1) Get-Min、Delete-Min 和 Merge 操作的优先级队列

Priority queue with O(1) Get-Min, Delete-Min and Merge operations

algorithm

heap

priority-queue

splay-tree