二叉堆简述

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