key
for referring to an item.You need numAccesses
as a key for priority queue.You need currentPos
to be able to quickly find a pq position of item by key.Now you organize hash map (key(Integer
) -> node(Node<T>
)) to quickly access items and min heap-based priority queue using number of accesses as priority. Now you can very quickly perform all operations (access, add new item, update number of acceses, remove lfu). You need to write each operation carefully, so that it maintains all the nodes consistent (their number of accesses, their position in pq and there existence in hash map). All operations will work with constant average time complexity which is what you expect from cache.O(log(n))
. This means, when the cache size is n
, the time needed to insert/remove an element into/from chache is logarithmic. Such implementations use usually a min heap
to maintain usage frequencies of elements. The root of the heap contains the element with lowest frequency, and can be accessed in O(1)
time. But to maintain the heap property we have to move an element, every time it is used (and frequency is incremented) inside of the heap, to place it into proper position, or when we have to insert new element into the cache (and so put it into the heap).But the runtime complexity can be reduced to O(1)
, when we maintain a hashmap
(Java) or unordered_map
(C++) with the element as key. Additinally we need two sorts of lists, frequency list
and elements lists
. The elements lists
contain elements that have same frequency, and the frequency list
contain the element lists
.frequency list
that has 4 elements (4 elements lists
). The element list 1
contains elements (a,c,m)
, the elements list 3
contains elements (k, l, n)
etc.Now, when we use say element y
, we have to increment its frequency and put it in the next list. Because the elements list with frequency 6 becomes empty, we delete it. The result is:elements list
7. When we have to remove elements from the list later, we will start from the end (first z
, then x
and then y
).Now, when we use element n
, we have to increment its frequency and put it into the new list, with frequencies 4:void set(key k, value v)
and bool get(key k, value &v)
. In the get method the value to retrieve will be set per reference when the element is found, in this case the method returns true. When the element is not found, the method returns false.