Структура данных для хранения пар ключ-значение и быстрого получения ключа для наименьшего значения

Question

Я реализую что-то вроде кеша, который работает так:

1. Если новое значение для данного ключа поступает от какого-либо внешнего процесса, сохраните это значение и запомните время, когда это значение пришло.
2. Если мы бездействуем, найдите в кеше самую старую запись, извлеките новое значение для ключа из внешнего источника и обновите кеш.
3. Возвращает значение для данного ключа при запросе.

Мне нужна структура данных для хранения пар ключ-значение, которая позволила бы выполнять следующие операции как можно быстрее (в порядке приоритета скорости):

1. Найдите ключ с самым низким (неизвестным) значением.
2. Обновите значение для данного ключа или добавьте новую пару ключ-значение, если ключ не существует.
3. Другие обычные операции с хеш-таблицами, такие как удаление ключа, проверка наличия ключа и т. Д.

Существуют ли структуры данных, которые позволяют это? Проблема здесь в том, что для быстрого выполнения первого запроса мне нужно что-то упорядоченное по значению, а для быстрого обновления значений для данного ключа мне нужно что-то упорядоченное по ключу. Лучшее решение, которое у меня есть, - это что-то вроде этого:

Сохраняет значения в обычной хеш-таблице и пары (значение, ключ) как упорядоченную по значению кучу. Поиск ключа для наименьшего значения выглядит следующим образом:

1. Найдите ключ для наименьшего значения в куче.
2. Найдите значение этого ключа из хеш-таблицы.
3. Если значения не совпадают, выведите значение из кучи и повторите процедуру с шага 1.

Обновление значений происходит следующим образом:

1. Сохраните значение в хеш-таблице.
2. Переместите новую пару (значение, ключ) в кучу.

Удаление ключа более сложное и требует поиска значения в куче. Это дает что-то вроде производительности O (log n), но это решение кажется мне громоздким.

Существуют ли какие-либо структуры данных, которые объединяют свойства хеш-таблицы для ключей и кучи для связанных значений? Я программирую на Python, поэтому, если в Python есть существующие реализации, это большой плюс.

Answer 1

Большинство реализаций кучи дадут вам самый низкий ключ в вашей коллекции за время O (1), но нет никаких гарантий относительно скорости случайного поиска или удаления. Я бы рекомендовал объединить две структуры данных: любую простую реализацию кучи и любую готовую хеш-таблицу.

Конечно, любое сбалансированное двоичное дерево можно использовать в качестве кучи, поскольку наименьшее и наибольшее значения находятся на крайнем левом и крайнем правом листьях соответственно. Красно-черное дерево или дерево AVL должны дать вам O (lg n) кучи и словарные операции.

Answer 2

Я бы попробовал:

import heapq

myheap = []
mydict = {}

...

def push(key, val):
    heapq.heappush(myheap, (val, key))
    mydict[key] = val

def pop():
    ...

Подробнее здесь

Answer 3

Вы ищете карту или ассоциативный массив. Чтобы получить более конкретную информацию, нам нужно знать, на каком языке вы пытаетесь использовать.