二叉堆简述
简述
对于堆,我个人的理解就是一种优先队列,从队列中取元素的时候总是取出最大(或最小)的元素。二叉堆是一种堆的一种实现形式,是一棵完全二叉树。对于二叉堆,我们显然可以分成两类:大根堆和小根堆,表示他每次取出的是最大元素还是最小元素。而大根堆一定是满足这样的一个性质,即:对于任意一个节点,他一定不大于他的父亲,而且不小于他的两个儿子。小根堆反之。
实现功能
以$O(n)$的时间建树,并以$O(logn)$的复杂度实现插入、寻找最小(或最大)值,修改元素,删除元素。
实现思路(小根堆)
我们用一个数组来储存数据,下标从1开始,对于第$i$个元素,他的左儿子为$i2$,他的右儿子为$i2+1$,当然对于非根节点,他的父亲就是$i/2$。在这里,这个数组用$heap[]$表示。
同时,我们用数组$id[i]$数组来表示第(i)个元素是第几个插入的,用$pos[i]$来表示第$i$个元素是第几个插入的(很明显有$id[pos[i]]=i$)。当然,根据实际情况,这两个东西可以不要。
这里要用到的最重要的两个函数是$up(i)$和$down(i)$函数, $up(i)$函数是将第$i$个元素上移,如果他比他的父亲大,就和他的父亲交换位置,即维护他比他父亲小的性质。$down(i)$函数类似,只是比较的是两个儿子中较小的那个。
接下来是算法的核心:
- 当加入一个元素时,我们把他加入到堆的底部,即heap数组的末尾,然后调用$up(i)$函数将其上移到合适位置。
- 当修改一个元素时,只要直接修改,然后分别调用$down(i)$函数和$up(i)$函数找到他适合的位置。
- 当删除堆顶元素的时候,我们只要把他和最后一个元素交换位置(这样只需要将数组大小减一就可以删掉他),然后用$down(i)$函数将堆顶元素下移到合适位置。
- 当删除任意元素时,只需要把他赋值为负无穷,然后上浮到堆顶,再利用删除堆顶元素的方法删除他。
基本模版
#include<algorithm>
using namespace std;
const int MAXSIZE = 100000;
struct Heap{
int heap[MAXSIZE];//记录堆的元素,下标从1开始
int n;//堆中元素的个数
int counter;//加入到堆中的元素的个数(考虑到被删除的元素)
int id[MAXSIZE];//第i个元素是第几个加入的
int pos[MAXSIZE];//第i个加入的元素的位置
Heap();//一个空的Heap
Heap(int *, int n);//用一个数组初始化Heap,数组下标从0开始
void push(int v);//添加元素v
void change(int i, int value);//把第i个加进去的元素修改为value
void pop();//删掉堆顶
void erase(int i);//删除第i个加进去的元素
void up(int i);//将数组中第i个元素上移
void down(int i);//将数组中第i个元素下移
int top();//返回堆顶元素
};
Heap::Heap(){
n = counter = 0;
}
Heap::Heap(int a[], int n){
n = counter = 0;
for (int i = 0; i < n; i++){
heap[++n] = a[i];
id[n] = pos[n] = n;
}
for (int i = n / 2; i >= 1; i--){
down(i);
}
}
void Heap::up(int i){
int x = heap[i], y = id[i];
for (int j = i / 2; j >= 1; j /= 2){
if (heap[j]>x){
heap[i] = heap[j];
id[i] = id[j];
pos[id[i]] = i;
i = j;
}
else{
break;
}
heap[i] = x;
id[i] = y;
pos[y] = i;
}
}
void Heap::down(int i){
int x = heap[i], y = id[i];
for (int j = i * 2; j <= n; j *= 2){
if (j<n&&heap[j]>heap[j + 1])
j++;
if (heap[j] < x){
heap[i] = heap[j];
id[i] = id[j];
pos[id[i]] = i;
i = j;
}
else{
break;
}
heap[i] = x;
id[i] = y;
pos[y] = i;
}
}
void Heap::push(int v){
heap[++n] = v;
id[n] = ++counter;
pos[counter] = n;
up(n);
}
int Heap::top(){
return heap[1];
}
void Heap::pop(){
swap(heap[1], heap[n]);
swap(id[1], id[n--]);
pos[id[1]] = 1;
down(1);
}
void Heap::change(int i, int value){
heap[pos[i]] = value;
down(pos[i]);
up(pos[i]);
}
void Heap::erase(int i){
heap[pos[i]] = heap[1] - 1;
up(pos[i]);
pop();
}