前言
话说新开的博客十分好用...
所以，我打算开一个坑，名曰【算法系列】。
什么意思——从名字泥应该就猜得出来。。。
废话不多说，进入正文~~
正文
原理
首先，堆是一颗棵二叉树。。
其次，堆是一棵完全二叉树。。
然后，设有一关系 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;