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

Question

我想知道是否有办法构建一个支持常量get-min,delete-min和merge操作的优先级队列结构.我不关心插入的时间复杂性,也不必支持reduce-key操作.我的用例在(坏)伪代码中:

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也是恒定时间,违反了已知的排序下限.