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

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

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.

Solution

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.