算法&数据结构系列 -- 堆(优先队列)

前言话说新开的博客十分好用...所以,我打算开一个坑,名曰【算法系列】。什么意思——从名字泥应该就猜得出来。。。废话不多说,进入正文~~正文原理首先,堆是一二叉树。。其次,堆是一棵完全二叉树。。然后,设有一关系 P(Type X, Type Y)则,堆的每个元素 Element满足:
foreach Child ∈ Element.Childs do
    ASSERT( P(Element.value, Child.value) );
说的明白点,就是每个元素和它的儿子有特定得关系。。。(忽略错别字)所以,利用堆の性质,我们可以在O(lg n)的时间复杂度内做一些好的事情。。。解释(?)& 代码1. 关于堆的存储设v是堆里一点,则:v*2 是 v的左儿子v*2+1 是 v的右儿子在实际操作中,我们常用位运算加速操作。即:
inline int LEFT(int x) {return (x<<1);}
inline int RIGHT(int x) {return (x<<1|1);}
inline int FATHER(int x) {return (x>>1);}
2. 初始化堆
heapnum = 0;
memset(heap, 0, sizeof(heap));
3. 维护堆的性质这是堆比较重要的一个函数。Heapify(x) 维护以为根的字树保持堆的性质。代码:
void Heapify(int x){
    int largest;
    if(LEFT(x) <= heapnum && P(heap[x],heap[LEFT(x)]))
        largest = LEFT(x);
    else largest = x;
    if(RIGHT(x) <= heapnum && P(heap[largest], heap[RIGHT(x)]))
        largest = RIGHT(x);
    if(largest != x){
        Exchange(heap[x], heap[largest]);
        Heapify(largest);
    }
}
4. UPDATE元素该函数的作用是把x元素改为y,且必须满足P(heap[x],y)
void HeapInc(int x,int y){
    heap[x] = y;
    while (x > 1 && P(heap[FATHER(i)], heap[x])) {
        Exchange(heap[x], heap[FATHER(x)]);
        x = FATHER(x);
    }
}
5. 添加元素不说了。。。上代码:附注:这里假设P(x,y)表示x<y, 如果P(x,y)表示x>y那么请用INF代替-INF
void HeapAdd(int x){
    heap[++heapnum] = -INF;
    HeapInc(heapnum, x);
}
6. 关于堆首的操作首先 --- 返回堆首元素(哈哈,这个不会写的话···)
int Top(){
    assert(heapnum >= 1); //assert(x)表示断言,如果x为false就停止程
    return heap[1];
}
其次 --- 删除堆首元素
void Pop(){
    assert(heapnum >= 1);
    Exchange(heap[1], heap[heapnum--]);
    if(heapnum) Heapify(1);
}
最后 --- 结合上面两个
int Extract(){
    int val = Top();
    Pop();
    return val;
}
7. 其他一些东西非空:
bool Empty(){
    return heapnum == 0;
}
8. 写成一个类神马是类?你猜····
const int N                =        30000;
const int HEAPSIZE        =        N * 4;

template <class TElement = int, class Operator = less<int> >
class BasicHeap{
private:
    TElement Plc;
    TElement heap[HEAPSIZE + 5];
    int heapnum;
    Operator P;
    inline int LEFT(int x){return x<<1;}
    inline int RIGHT(int x){return x<<1|1;}
    inline int FATHER(int x){return x>>1;}
    inline void Exchange(TElement & x, TElement & y){TElement t = x; x = y; y = t;}
    void Heapify(int x){
        int largest;
        if(LEFT(x) <= heapnum && P(heap[x],heap[LEFT(x)]))
            largest = LEFT(x);
        else largest = x;
        if(RIGHT(x) <= heapnum && P(heap[largest], heap[RIGHT(x)]))
            largest = RIGHT(x);
        if(largest != x){
            Exchange(heap[x], heap[largest]);
            Heapify(largest);
        }
    }
    inline void Assert(bool flg){
        if(!flg){
            abort();
        }
    }
public:
    BasicHeap(){
        heapnum = 0;
        P = Operator();
    }
    void Inc(int x,int y){
        heap[x] = y;
        while (x > 1 && P(heap[FATHER(x)], heap[x])) {
            Exchange(heap[x], heap[FATHER(x)]);
            x = FATHER(x);
        }
    }
    void Add(int y){
        heap[++heapnum] = y;
        int x = heapnum;
        while (x > 1 && P(heap[FATHER(x)], heap[x])) {
            Exchange(heap[x], heap[FATHER(x)]);
            x = FATHER(x);
        }
    }
    int Top(){
        Assert(heapnum >= 1);
        return heap[1];
    }
    void Pop(){
        Assert(heapnum >= 1);
        Exchange(heap[1], heap[heapnum--]);
        if(heapnum) Heapify(1);
    }
    int Extract(){
        int val = Top();
        Pop();
        return val;
    }
    void Clear(){
        heapnum = 0;
    }
    bool Empty(){
        return heapnum == 0;
    }
};
typedef BasicHeap<> MaxHeap;
typedef BasicHeap<int, greater<int> > MinHeap;

相关内容推荐