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

Question

I'm wondering if there is a way to construct a priority queue structure that supports constant-time get-min, delete-min, and merge operations. I don't care about the time complexity of insertions and it doesn't have to support the decrease-key operation. My use case in (bad) pseudo-code:

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

I've considered splay trees (in particular, https://cs.stackexchange.com/questions/524/does-there-exist-a-priority-queue-with-o1-extracts) and Fibonacci heaps, but they don't seem to satisfy these requirements.

I don't think it's possible. Constant-time merging would allow to build queue of n elements in O(n), with constant-time delete-min it would allow to sort elements in O(n). — Marcin Łoś

David Eisenstat David Eisenstat · Accepted Answer · 2015-03-02T15:13:18

This is impossible if priorities can be compared only. The problem is that a constant-time merge can be used to simulate insert in constant time, which, since delete-min also is constant-time, violates the known lower bound on sorting.

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

1 Answers