hash heap template

12个函数

code

class hashheap {
public:
    vector<int> heap;
    unordered_map<int, node> hash;
    int count;
    int mode;

    hashheap(int mode)
    {
        this->mode = mode;
    }

    int size()
    {
        return count;
    }

    int top()
    {
        return heap[0];
    }

    bool isEmpty()
    {
        return count == 0;
    }

    int parent(int id)
    {
        if(id == 0)
        {
            return -1;
        }
        return (id-1)/2;
    }

    int lson(int id)
    {
        return id*2 + 1;
    }

    int rson(int id)
    {
        return id*2 + 2;
    }

    bool comparesmall(int a, int b)
    {
        if(a <= b)
        {
            if(mode == 0)
            {
                return true;
            }
            else
            {
                return false;
            }
        }
        else
        {
            if(mode == 0)
            {
                return false;
            }
            else
            {
                return true;
            }
        }
    }

    void swap(int ida, int idb)
    {
        int vala = heap[ida];
        int valb = heap[idb];

        int numa = hash[vala].num;
        int numb = hash[valb].num;

        hash[vala] = node(idb, numa);
        hash[valb] = node(ida, numb);

        heap[ida] = valb;
        heap[idb] = vala;
    }

    void siftup(int id)
    {
        while(parent(id) != -1)
        {
            int p = parent(id);
            if(comparesmall(heap[p], heap[id]) == true)
            {
                break;
            }
            else
            {
                swap(p, id);
            }
                id = p;
        }
    }

    void siftdown(int id)
    {
        while(lson(id) < heap.size())
        {
            int lid = lson(id);
            int rid = rson(id);
            int son;
            if(rid >= heap.size() || comparesmall(heap[lid], heap[rid]))
            {
                son = lid;
            }
            else
            {
                son = rid;
            }

            if(comparesmall(heap[id], heap[son]))
            {
                break;
            }
            else
            {
                swap(id, son);
            }
                id = son;
        }
    }

    void add(int val)
    {
        count++;
        if(hash.find(val) != hash.end())
        {
            hash[val].num++;
        }
        else
        {
            int idx = heap.size();
            heap.push_back(val);
            hash[val] = node(idx, 1);

            siftup(idx);
        }
    }

    int pop()
    {
        count--;
        int now = heap[0];
        if(hash[now].num > 1)
        {
            hash[now].num--;
        }
        else
        {
            swap(0, heap.size()-1);
            heap.pop_back();
            hash.erase(now);
            if(heap.size() > 0)
            {
                siftdown(0);
            }

        }

        return now;
    }

    void remove(int now)
    {
        count--;
        if(hash[now].num > 1)
        {
            hash[now].num--;
        }
        else
        {
            int idx = hash[now].id;

            swap(idx, heap.size()-1);
            heap.pop_back();
            hash.erase(now);
            if(heap.size() > idx)
            {

                siftdown(idx);
                siftup(idx);
            }
        }
    }
};