CC++ 二叉堆

二叉堆是一棵满足“堆性质”的完全二叉树。

以小根堆为例，其“堆性质”是指：树上每个结点的权值都小于等于其左右子节点的权值。

（大根堆则反之）
根据完全二叉树的性质，可在存储时令下标为x的结点的左子结点下标为2x，右子结点下标为2x+1。

以小根堆为例，分别进行插入（Insert）、移除堆顶（Extract）、移除任意结点（Remove） *** 作。

# include 
using namespace std;


const int INF = ~(1<<31);

TYPE SH[SIZE];  // 定义小根堆
int tail;  // tail指向堆中最末尾的元素

// main
SH[0] = -INF, tail = 0;  // 初始化，重要！！

Insert

向二叉堆中插入一个权值为val的新节点。

时间复杂度：O(logN)

• 把这个新节点直接存储在二叉堆的末尾，通过交换的方式向上调整至满足堆性质。
  

  
  

void Insert(TYPE val) {
	int p = ++ tail; SH[p] = val;
	while (val < SH[p>>1]) swap(SH[p], SH[p>>1]), p >>= 1;
}

// main
Insert(val);

Extract

把堆顶从二叉堆中移除。

时间复杂度：O(logN)

• 把堆顶元素与末尾元素交换，删除末尾结点，并把堆顶通过交换的方式向下调整至满足堆性质。
  

  
  

void Extract() {
	SH[1] = SH[tail --]; int p = 1;
	while (p<<1 <= tail) {
		TYPE t = min(SH[p<<1], (p<<1)+1 <= tail ? SH[(p<<1)+1] : INF);
		if (SH[p] <= t) break;
		p <<= 1; if (t != SH[p]) p += 1;
		swap(SH[p>>1], SH[p]);
	}
}

// main
Extract();

Remove

把下标为p的结点从二叉堆中删除。

时间复杂度：O(logN)

• 把下标为p的结点与末尾元素交换，删除末尾结点，并把“新p结点”通过交换的方式分别向上、向下调整至满足堆性质。
  

  
  

void Remove(int p) {
	SH[p] = SH[tail --];
	while (SH[p] < SH[p>>1]) swap(SH[p], SH[p>>1]), p >>= 1;  // 向上调整
	while (p<<1 <= tail) {  // 向下调整
		TYPE t = min(SH[p<<1], (p<<1)+1 <= tail ? SH[(p<<1)+1] : INF);
		if (SH[p] <= t) break;
		p <<= 1; if (t != SH[p]) p += 1;
		swap(SH[p>>1], SH[p]);
	}
}

// main
Remove(p);