适妞

[html] 
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; 
    } 
}; 

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;
    }
};