Is there a Python data structure that seamlessly combines a dictionary (with nested dictionaries or lists as values) and a heap, allowing sorting based on a specific value within the nested structures?
cache = {"key1": {"time": time1, "info": "key1 info"}, "key2": {"time": time2, "info": "key2 info"}, ...}
or:
cache = {"key1": [time1, "key1 info"], "key2": [time2, "key2 info"], ...}
here time1
, time2
, ... is the time of insertion or update of the entry.
The goal is to implement an efficient cache, checking key existence, validating the value's freshness (as it becomes outdated over time), and removing the oldest key when the cache is full. The dictionary should support heap operations either by using the nested key "time" or the zeroth element of the list.
Current options considered:
- Forming a heap from the dictionary (drawback - expensive operation O(n^2)).
- Implementing a class with separately stored heap and dictionary (drawback - complexity of synchronizing data in the heap and dictionary).
- Simple iteration through the dictionary in O(n). This option is favored for its simplicity but might not be optimal.
Is there a more efficient solution or a different approach that avoids creating a custom data structure?