460. LFU Cache

class LFUCache {
public:
    LFUCache(int capacity) {
        cap = capacity;
        minFreq = 0;
    }

    int get(int key) {
        auto idx = mit.find(key);
        if (idx != mit.end()) {
            freqs[idx->second.first].erase(idx->second.second);
            if (freqs[minFreq].empty()) minFreq++;
            freqs[++idx->second.first].push_back(key);
            idx->second.second = --freqs[idx->second.first].end();
            return cache[key];
        }
        return -1;
    }

    void put(int key, int value) {
        if(cap<=0) return;  //pay attention to this shit!!!!
        if (get(key) == -1) {
            if (cache.size() == cap) {
                int eraseK = freqs[minFreq].front();
                freqs[minFreq].pop_front();
                cache.erase(eraseK);
                mit.erase(eraseK);
            }
            freqs[1].push_back(key);
            mit[key] = {1, --freqs[1].end()};
            minFreq = 1;
        }
        cache[key] = value;
    }
private:
    unordered_map <int, list<int>> freqs;   //freqs to list of keys
    unordered_map <int, int> cache;     //key to value
    unordered_map <int, pair<int, list<int>::iterator>> mit;    //key to freqs and iterator
    int cap, minFreq;
};

/**
 * Your LFUCache object will be instantiated and called as such:
 * LFUCache obj = new LFUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */

index priority queue

Use it to impress your interviewer!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

class LFUCache {
public:
    struct Node {
        int key; // key of the element.
        int val; // value of the ement.
        int fre; // usage frequency
        int timeStamp; // the latest time stamp when this element is accessed.
        Node(): key(-1), val(-1), timeStamp(-1), fre(0) {}
        Node(int k, int v, int ts): key(k), val(v), timeStamp(ts), fre(1) {}
    };

    LFUCache(int capacity) {
        Cap = capacity;
        Node* dummy = new Node();
        pq.push_back(dummy); // The pq start from pq[1].
        ts = 0;
    }

    int get(int key) {
        if(!mp.count(key)) return -1;
        int index = mp[key];
        int val = pq[index]->val;
    pq[index]->fre++;
    pq[index]->timeStamp = ++ts;
        sink(index);
        return val;
    }

    void set(int key, int value) {
        if(Cap <= 0) return;
    if(mp.count(key)) {
       int index = mp[key];
       pq[index]->val = value;
       get(key);
    }
    else {
        if(pq.size() - 1 == Cap) {
            int oldKey = pq[1]->key;
        mp.erase(oldKey);
        Node* newnode = new Node(key, value, ++ts);
        pq[1] = newnode;
        mp[key] = 1;
        sink(1);
        }
        else {
            Node* newnode = new Node(key, value, ++ts);
        pq.push_back(newnode);
        mp[key] = pq.size() - 1;
        swim(pq.size() - 1);
        }
    }
    }

private:
    vector<Node*> pq; // A priority queue, with the least usage frequency and least recently used element at the top.
    unordered_map<int, int> mp; // A mapping from the key of the element to its index in the priority queue.
    int Cap; // Capcity of the cache
    int ts; // time-stamp: indicate the time stamp of the latest operation of an element. According to the requirement of LFU cache, when we need to evict an element from the cache, but there are multiple elements with the same minimum frequency, then the least recently used element should be evicted.

    /*
     * Recursively sink a node in priority queue. A node will be sinked, when its frequency is larger than any of its
     * children nodes, or the node has the same frequency with a child, but it is recently updated. 
     */
    void sink(int index) {
        int left = 2 * index, right = 2 * index + 1, target = index;
        if(left < pq.size() && pq[left]->fre <= pq[target]->fre) // If the left child has the same frequency, we probably need to swap the parent node and the child node, because the parent node is recently accessed, and the left child node was accessed at an older time stamp.
               target = left;
            if(right < pq.size()) { 
                if(pq[right]->fre < pq[target]->fre || (pq[right]->fre == pq[target]->fre && pq[right]->timeStamp < pq[target]->timeStamp)) // If right child has the same frequency and an older time stamp, we must swap it.
                     target = right;
        }
        if(target != index) {
            myswap(target, index);
                sink(target);
        }
    }

    /*a
     * Recursively swim a node in priority queue. A node will be swimmed, when its frequency is less than its
     * parent node. If the node has the same frequency with its parent, it is not needed to be swimmed, because
     * it is recently accessed.
     */
    void swim(int index) {
        int par = index / 2;
        while(par > 0 && pq[par]->fre > pq[index]->fre) {
            myswap(par, index);
        index = par;
        par /= 2;
        }
    }

    void myswap(int id1, int id2) {
        swap(pq[id1], pq[id2]);
        mp[pq[id1]->key] = id1;
        mp[pq[id2]->key] = id2;
    }
};