Priority queue usage in LRU cache?


#1

How to use priority queue in LRU cache ? Discuss the flow and over all design


#2

Alone priority queue will not be sufficient for LRU implementation. You will need hash map along with it.
Below is the flow diagram

In hash map, k1,k2,k3… will be the keys corresponding to cache. The value will be the address(index) of priority queue where the actual value is stored along with one more parameter c(counter). Priority queue will use only c in its compare method to determine the priority of that element.
C will be nothing but a simple counter which will increase for every operation. So suppose we start to put (k1,v1) in cache,c will be 0. Next put (k2,v2), c will be 1. next retrieve value for k1, c will be 2. `put (k3,v3), c will be 3.
For put operation(k,v), we will first increase c, insert (v,c) in priority queue and get index, insert (k, index) in map.
For retrieve(value corresponding to k), increase c,get index from map for k, get value from priority queue at index which will be (v, counter). update value with (v, c) (counter -> c) and return v.