#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;
}
}
}
标签:std,queue,Java,为例,priorityQueue,键值,key,pair,const
From: https://www.cnblogs.com/HuXinIO/p/17860693.html