Как сделать эффективное приоритетное обновление в STL priority_queue?
Ниже приведен простой пример, который может вам помочь:
json_string = """
{
"pk": 1,
"fa": "cc.ee",
"fb": {
"fc": "",
"fd_id": "12345"
}
}"""
import json
data = json.loads(json_string)
if data["fa"] == "cc.ee":
data["fb"]["new_key"] = "cc.ee was present!"
print json.dumps(data)
Выход для вышеуказанного кода будет:
{"pk": 1, "fb": {"new_key": "cc.ee was present!", "fd_id": "12345",
"fc": ""}, "fa": "cc.ee"}
Обратите внимание, что вы можете установить аргумент ident дамп распечатать его так (например, при использовании print json.dumps (data, indent = 4)):
{
"pk": 1,
"fb": {
"new_key": "cc.ee was present!",
"fd_id": "12345",
"fc": ""
},
"fa": "cc.ee"
}
4 ответа
Я думаю, что Вам не повезло со стандартной приоритетной очередью, потому что Вы не можете достигнуть базовую двухстороннюю очередь/вектор/список или что бы то ни было. Необходимо реализовать собственное - дело не в этом трудно.
Можно хотеть взглянуть на replace_if с примером здесь .
Самый простой способ сделать это с помощью STL (который я знаю) - удалить запись, обновить ее приоритет и затем снова вставить. Это довольно медленно с использованием std :: priority_queue, однако вы можете сделать то же самое с std :: set. К сожалению, вы должны быть осторожны, чтобы не изменить приоритет объекта, когда он находится в наборе.
Я реализовал класс mutable_priority_queue, объединяющий std :: multimap (для сопоставления приоритета с значением) и std :: map (для сопоставления значения с приоритетом), который позволяет вставлять / удалять элементы, а также обновлять существующие значения в логарифмическом времени. Вы можете получить код и пример того, как его использовать здесь
Соответствующая структура данных называется "куча Фибоначчи". Но вам нужно реализовать ее самостоятельно. Вставка/обновление - O(1) ExtractMin - O(logn)