Mythsman


乐极生悲,苦尽甘来。


二叉堆简述

简述

对于堆,我个人的理解就是一种优先队列,从队列中取元素的时候总是取出最大(或最小)的元素。二叉堆是一种堆的一种实现形式,是一棵完全二叉树。对于二叉堆,我们显然可以分成两类:大根堆和小根堆,表示他每次取出的是最大元素还是最小元素。而大根堆一定是满足这样的一个性质,即:对于任意一个节点,他一定不大于他的父亲,而且不小于他的两个儿子。小根堆反之。

实现功能

以$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();
}