I'd maintain a min heap structure where every block has a node corresponding to it. And in each block I'll keep the count of the number of times this node was accessed. The root node will have the minimum count; thus when the cache becomes full, it is simply removed in O(1) time. However, if the root node is accessed again, its count is increased by 1. If a shuffle needs to be made then, we perform heapification techniques on this node and find a new root for the heap