学步园

适妞

namespace MappingBinaryHeap{
/*
    DS:
        Datastructure to show the value
    Heap:
        1.Ds:value
        2.idx:index
    pos:
        The position for each index
    len:
        The volum n of heap
    hh:
        heap
    Push:
        insert an element
    Pop:
        pop an element:
            1.pop(pos[]) pop the element index
            2.pop(1) pop the 'max' one
*/
    struct DS{
        int next;
        DS(){}
        DS(int x) : next(x){}
        bool operator <(const DS &A) const {
            if (next == -1)
                return true;
            if (A.next == -1)
                return false;
            return next > A.next;
        }
        void init() {
            next = 0;
        }
    };
    #define maxn 100005
    struct Heap {
        int idx;
        DS val;
    }hh[maxn];
    int pos[maxn];
    int len;
    bool Prior(Heap a, Heap b) {
        return a.val < b.val;
    }
    void Push(Heap s) {
        int i;
        for (i = ++len; i > 1 && Prior(s, hh[i / 2]); i /= 2) {
            hh[i] = hh[i / 2];
            pos[hh[i].idx] = i;
        }
        hh[i] = s;
        pos[hh[i].idx] = i;
    }
    Heap Pop(int idx) {
        if (idx == -1)
            return hh[0];
        Heap ret = hh[idx];
        Heap last = hh[len--];
        int i, s;
        for (i = idx; i * 2 <= len; i = s) {
            s = i * 2;
            if (s + 1 <= len && Prior(hh[s + 1], hh[s])) {
                s++;
            }
            if (Prior(hh[s], last)) {
                hh[i] = hh[s];
                pos[hh[i].idx] = i;
            } else {
                break;
            }
        }
        hh[i] = last;
        pos[hh[i].idx] = i;
        for (i = idx; i > 1 && Prior(hh[i], hh[i / 2]); i /= 2) {
            Heap buf = hh[i];
            hh[i] = hh[i / 2];
            hh[i / 2] = buf;
            pos[hh[i].idx] = i;
            pos[hh[i / 2].idx] = i / 2;
        }
        return ret;
    }
    void init() {
        hh[0].val.init();
        len = 0;
    }
};