双标准优先级队列

Question

是否有一个不太复杂的方法来实现使用两个标准的优先级队列？队列获取与2个中创建ComparatorS和提供(除了add)的操作poll1()和poll2(),其中每个删除和返回根据相应的比较器的最小元素.

请注意,它与这两个 问题没有任何共同之处.

动机

我的用例是分支定界优化.当您获得无限时间时,以最佳界限扩大候选人可证明是最佳的.假设无限时间可证明是错误的.

严格遵循这一策略通常最终在截止日期到来时根本没有解决方案.一个简单的创可贴首先是将搜索引向解决方案,然后切换到最佳约束策略.这是相当不令人满意的,因为发现的第一个解决方案可能是任意低质量的.

这就是为什么我想使用两个标准队列:在一个步骤中,展开最佳边界候选者,在另一个步骤中,根据一些启发式扩展"最佳外观"候选者.

另一种可能的用途是用于帕累托最优化.

Answer 1

该任务的目标是为目标优先级队列维持相同的摊销运行时间。

这些运行时O(log n)用于插入和删除。

维护两个优先级队列，每个队列都有自己的比较器。维护添加的对象的计数图。当对象从队列中删除时，计数就会减少。如果您尝试从队列中轮询的对象的计数 <= 0，则轮询另一个项目。

以下实现维护运行时。它已O(log n)针对插入和移除进行了摊销。因为每个元素只添加到每个队列中并从每个队列中删除一次，所以它必须是单个队列运行时间的常量倍数。此外，映射的插入和删除时间为O(1)，这不会影响O(log n)队列的运行时间。

public class DualPriorityQueue<T> {

    private Queue<T> queue1, queue2;
    private Map<T, Integer> counts;

    public DualPriorityQueue(int size, Comparator<T> c1, Comparator<T> c2) {
        queue1 = new PriorityQueue(size, c1);
        queue2 = new PriorityQueue(size, c2);
        counts = new HashMap<T, Integer>(size);
    }

    public T poll1() {
        return poll(queue1);
    }

    public T poll2() {
        return poll(queue2);
    }

    private T poll(Queue<T> queue) {
        T t = null;
        while (!queue.isEmpty() && !removeCount(t = queue.poll())) {
            t = null;
        }
        return t;
    }

    public boolean offer(T t) {
        queue1.offer(t);
        queue2.offer(t);
        addCount(t);
        return true;
    }

    private boolean removeCount(T t) {
        final Integer value = counts.get(t);
        if (value != null && value > 0) {
            final int newValue = value - 1;
            if (newValue == 0) {
                counts.remove(t);
            } else {
                counts.put(t, newValue);
            }
            return true;
        }
        return false;
    }

    private void addCount(T t) {
        final Integer prev = counts.get(t);
        if (prev == null || prev <= 0) {
            counts.put(t, 1);
        } else {
            counts.put(t, prev + 1);
        }
    }
}