Heap（最大堆/最小堆）

C++ STL 有提供priority_queue，但是它没有接口修改已经加入队列的元素的优先级。有时候我们希望修改队列中元素的优先级，可以通过priority_queue + 最后更新的时间戳，例如用一个map或unordered_map存储每个key最后更新的时间戳，然后将重复的key和priority的pair加入到priority_queue中，在取得队头元素时根据时间戳判断是否丢弃，这可以解决大多数问题，但如果遇到插入和更新特别多的情况，为了避免priority_queue迅速膨胀，我们不得不自己实现最大堆。

实际上通过之前讲过的Treap稍加改造就可以得到一个可以动态更新key优先级的Heap

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

namespace detail {

template<typename KT, typename PT>
struct TreeNode {
    KT key;
    PT priority;
    int size;
    TreeNode* left;
    TreeNode* right;

    TreeNode(const KT& key, const PT& priority):key(key),priority(priority),size(1),left(NULL),right(NULL){}
};

template<typename KT, typename PT>
class TreeNodePool {
    int batchsize = 1024;
    vector<char*> memchunks;
    queue<char*> blocks;
public:
    ~TreeNodePool() {
        for(int i=0;i<memchunks.size();i++) {
            free(memchunks[i]);
        }
    }

    TreeNode<KT, PT>* create(const KT& key, const PT& priority) {
        if(blocks.empty()) {
            char* p = (char*)malloc(sizeof(TreeNode<KT, PT>)*batchsize);
            memchunks.emplace_back(p);
            for(int i=0;i<batchsize;i++) {
                blocks.push(p+sizeof(TreeNode<KT, PT>)*i);
            }
            batchsize *= 2;
        }
        char* p = blocks.front(); blocks.pop();
        return new (p)TreeNode<KT, PT>(key, priority);
    }

    void release(TreeNode<KT, PT>* p) {
        blocks.push((char*)p);
    }
};
} // namespace detail

template<typename KT, typename PT, typename CMPF=less<PT> >
class Heap {
public:
    // 插入或更新key对应的priority
    void upsert(const KT& key, const PT& priority) {
        erase(key);
        insert(key, priority);
    }
    // 查看堆顶key
    const KT& peek() const {
        return root->key;
    }
    KT& peek() {
        return root->key;
    }
    // 取出堆顶key
    KT pop() {
        KT result = peek();
        erase(result);
        return result;
    }

    bool empty() const {
        return size() == 0;
    }

    int size() const {
        return _size(root);
    }

private:
    int insert(const KT& key, const PT& priority) {
        return _insert(root, create_tree_node(key, priority));
    }

    void erase(const KT& key) {
        _erase(root, key);
    }

private:
    detail::TreeNode<KT, PT>* create_tree_node(const KT& key, const PT& priority) {
        return pool.create(key, priority);
    }
    
    void release_tree_node(detail::TreeNode<KT,PT>* root) {
        pool.release(root);
    }

    static int _size(detail::TreeNode<KT,PT>* root) {
        return (root != NULL ? root->size : 0);
    }

    // 返回root子树的size减去左右子树的size
    static int _count(detail::TreeNode<KT,PT>* root) {
        if(root == NULL) return 0;
        return _size(root) - _size(root->left) - _size(root->right);
    }

    static void lrotate(detail::TreeNode<KT,PT>* &root) {
        auto right = root->right;
        auto rightleft = right->left;
        root->right = rightleft;
        right->left = root;
        int root_size = root->size;
        root->size += _size(rightleft) - _size(right);
        right->size = root_size;
        root = right;
    }

    static void rrotate(detail::TreeNode<KT,PT>* &root) {
        auto left = root->left;
        auto leftright = left->right;
        root->left = leftright;
        left->right = root;
        int root_size = root->size;
        root->size += _size(leftright) - _size(left);
        left->size = root_size;
        root = left;   
    }

    int _insert(detail::TreeNode<KT,PT>* &root, detail::TreeNode<KT,PT>* p) {
        if(root == NULL) {
            root = p;
            return 1;
        } else {
            if(p->key < root->key) {
                int r = _insert(root->left, p);
                root->size += r;
                if(CMPF()(root->priority, root->left->priority)){
                    rrotate(root);
                }
                return r;
            } else if(root->key < p->key) {
                int r = _insert(root->right, p);
                root->size += r;
                if(CMPF()(root->priority, root->right->priority)){
                    lrotate(root);
                }
                return r;
            } else {
                root->size += 1;
                release_tree_node(p);
                return 1;
            }
        }
    }

    static int _count(detail::TreeNode<KT,PT>* root, const KT& key) {
        if(root == NULL) return 0;
        if(key < root->key) return _count(root->left, key);
        else if(root->key < key) return _count(root->right, key);
        else return _count(root);
    }

    int _erase(detail::TreeNode<KT,PT>* &root, const KT& key) {
        if(root == NULL) return 0;
        if(key == root->key) {
            auto left = root->left;
            auto right = root->right;
            if(left == NULL) {
                int root_count = _count(root);
                release_tree_node(root);
                root = right;
                return root_count;
            } else if(right == NULL) {
                int root_count = _count(root);
                release_tree_node(root);
                root = left;
                return root_count;
            } else {
                int root_count = _count(root);
                int r = 0;
                if(CMPF()(left->priority, right->priority)) {
                    lrotate(root); // 把优先级大的孩子转成根
                    r = _erase(root->left, key);
                } else {
                    rrotate(root);
                    r = _erase(root->right, key);
                }
                root->size -= r;
                return r;
            }
        } else if(key < root->key) {
            int r = _erase(root->left, key);
            root->size -= r;
            return r;
        } else {
            int r = _erase(root->right, key);
            root->size -= r;
            return r;
        }
    }

private:
    detail::TreeNodePool<KT, PT> pool;
    detail::TreeNode<KT, PT>* root = NULL;
};