526互联

支持修改键值的优先队列（以C++，Java为例）

发布时间 2023-11-27 22:28:12作者: 最最最長的電影
#include <queue>
#include <functional>

template<typename T1, typename T2>
class mutable_priority_queue;

template<typename T1, typename T2>
class mutable_priority_queue {
private:
    std::function<bool(const std::pair<T1, T2> &, const std::pair<T1, T2> &)> comparator;
    std::priority_queue<std::pair<T1, T2>, std::vector<std::pair<T1, T2>>, decltype(comparator)> priorityQueue;
    std::unordered_map<T1, T2> Value;
    std::unordered_map<T1, bool> inQueue;

    bool check_in_queue(const std::pair<T1, T2> &);

public:
    explicit mutable_priority_queue(const std::function<bool(const T2 &, const T2 &)> &cmp
    = [](const T2 &o1, const T2 &o2) {
        return o1 > o2;
    });

    void push(const T1 &key, const T2 &value);

    std::pair<T1, T2> top();

    void pop();

    void remove_key(const T1 &key);

    size_t size();
};

template<typename T1, typename T2>
mutable_priority_queue<T1, T2>::mutable_priority_queue(const std::function<bool(const T2 &, const T2 &)> &cmp) :
        comparator([cmp](const std::pair<T1, T2> &o1, const std::pair<T1, T2> &o2) {
            return cmp(o1.second, o2.second);
        }), priorityQueue(comparator) {}


template<typename T1, typename T2>
bool mutable_priority_queue<T1, T2>::check_in_queue(const std::pair<T1, T2> &pair) {
    return inQueue[pair.first] && Value[pair.first] == pair.second;
}

template<typename T1, typename T2>
size_t mutable_priority_queue<T1, T2>::size() {
    size_t size = 0;
    for (const auto &pair: inQueue) {
        size += pair.second;
    }
    return size;
}

template<typename T1, typename T2>
void mutable_priority_queue<T1, T2>::remove_key(const T1 &key) {
    inQueue[key] = false;
}

template<typename T1, typename T2>
void mutable_priority_queue<T1, T2>::push(const T1 &key, const T2 &value) {
    Value[key] = value;
    inQueue[key] = true;
    priorityQueue.emplace(key, value);
}

template<typename T1, typename T2>
void mutable_priority_queue<T1, T2>::pop() {
    if (!priorityQueue.empty()) {
        auto topElement = top();
        inQueue[topElement.first] = false;
        priorityQueue.pop();
    }
}

template<typename T1, typename T2>
std::pair<T1, T2> mutable_priority_queue<T1, T2>::top() {
    while (!priorityQueue.empty() && !check_in_queue(priorityQueue.top())) {
        priorityQueue.pop();
    }
    return priorityQueue.top();
}

import java.util.Comparator;
import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

class MutablePriorityQueue<T1, T2> {
    private final Map<T1, T2> map = new HashMap<>();
    private PriorityQueue<Pair> priorityQueue = null;

    MutablePriorityQueue(Comparator<T2> comparator) {
        priorityQueue = new PriorityQueue<>((o1, o2) -> comparator.compare(o1.value, o2.value));
    }

    private boolean judgeInQueue(Pair pair) {
        return map.containsKey(pair.key) && map.get(pair.key) == pair.value;
    }

    public Pair peek() {
        while (!priorityQueue.isEmpty() && !judgeInQueue(priorityQueue.peek())) {
            priorityQueue.poll();
        }
        return priorityQueue.peek();
    }

    public Pair poll() {
        Pair pair = peek();
        map.remove(pair.key);
        return pair;
    }

    public void add(T1 Key, T2 Value) {
        priorityQueue.add(new Pair(Key, Value));
        map.put(Key, Value);
    }

    public void removeKey(T1 Key) {
        map.remove(Key);
    }

    public int size() {
        return map.size();
    }

    public class Pair {
        public T1 key;
        public T2 value;

        public Pair(T1 k, T2 v) {
            key = k;
            value = v;
        }
    }
}