# 概述

# 二叉堆

堆 (heap) 一般指二叉堆 (binary heap). 其采用数组进行实现，元素间构成一棵完全二叉树。堆可以便捷的实现最大 (或最小) 元素的查找，以及元素的插入删除。但元素的搜索效率低下。因此，堆的最典型的应用包括优先队列和堆排序。并查集也可以看作堆思想的一种体现。

堆的一个基本性质是：各元素与其父亲之间具有固定的大小关系，即 A[parent(i)] >= A[i] (或 <= ). 于是，根据大小关系的不同，堆可以分为两种形式：大根堆 (max-heap) 和小根堆 (min-heap)。若父亲节点的值大于子节点的值，那么根节点的值最大，即为大根堆，否则为小根堆。在 C++ STL 中，一般使用 <queue> 中的优先队列 priority_queue 实现堆。

# 其它的堆

其它的堆一般也是借助树结构实现的，包括左偏树、二项堆和斐波那契堆等。

其复杂度如下：

操作	配对堆	二叉堆	左偏树	二项堆	斐波那契堆
插入 (insert)	$O(1)$	$O(\log n)$	$O(\log n)$	$O(1)$	$O(1)$
查询最小值 (find-min)	$O(1)$	$O(1)$	$O(1)$	$O(\log n)$	$O(1)$
删除最小值 (delete-min)	$O(\log n)$	$O(\log n)$	$O(\log n)$	$O(\log n)$	$O(\log n)$
合并 (merge)	$O(1)$	$O(n)$	$O(\log n)$	$O(\log n)$	$O(1)$
减小一个元素的值 (decrease-key)	$o(\log n)$ (下界 $\Omega(\log \log n)$ , 上界 $O(2^{2\sqrt{\log \log n}})$ )	$O(\log n)$	$O(\log n)$	$O(\log n)$	$O(1)$
是否支持可持久化	$\times$	$\checkmark$	$\checkmark$	$\checkmark$	$\times$

# 二叉堆实现

以小根堆为例。

# 存储方式

手动实现的二叉堆一般以数组存储。这样，容易建立父亲节点与左右孩子的下标关系。

堆定义

	int h[MAXN];
	int h_size = 0;
	int ls(int p) {return p>>1;} // left son
	int rs(int p) {return p>>1\|1;} // right son

# 堆的性质维护

堆的性质维护采用 HEAPIFY （堆化）实现。在这里，我们需要维护子节点的值均小于父亲节点的值。若某个节点不符合堆的性质，那么我们可以让其上浮 / 下沉，直到其位于一个合适的位置。下沉操作中，需要将父亲节点与孩子节点中较小 (若为小根堆) 的那个交换位置。上浮操作则需要与父亲交换位置。上述两个操作统称为堆化 (heapify). 下面是一个小根堆的下沉堆化操作实现。

heapify_down

	void min_heapify_down(int p) {
	int l = ls(p);
	int r = rs(p);
	int min = (h[l]<h[r])?l:r;
	if (h[p]>h[min]) {
	swap(&(h[p]), &(h[min]));
	}
	min_heapify_down(int min);
	}

另外，也可以使用上浮的堆化操作。

heapify_up

	void min_heapify_up(int p) {
	int x = p;
	while (x>1 && h[x] < h[x>>1]) {
	swap(&(h[x]), &h[x>>1]);
	x >>= 1;
	}
	}

不论使用何种堆化函数，函数执行的次数不超过 $h$ 次，其中 $h$ 是二叉堆的高度。于是，堆化操作的复杂度为 $O(\log n)$ .

需要注意，每一次 heapify 操作只会使一个节点到其合适的位置。因此进行堆排序 & 建堆时，需要对全部 $n$ 个节点 (Maybe $\lceil n/2 \rceil$ ) 以合适的顺序进行堆化。所以堆排序和建堆的复杂度是 $O(n \log n)$ 的。

# 建堆

建堆的操作简单，只需要先将数据放到堆空间中，然后对二叉堆中所有非叶子节点执行一次堆化操作即可，共 $[n/2]$ 次。这样的复杂度是 $O(n\log n)$ 的。

	void build_min_heap() {
	for (int i = h_size/2; i>=0; i--) {
	min_heapify(i);
	}
	}

# 插入元素

在堆中插入一个元素，就是将其先放在堆底，然后执行上浮堆化操作，直到堆的性质得到满足。因此，插入的复杂度为 $O(\log n)$ .

insert

	void insert(int m) {
	h[h_size++] = m;
	min_heapify_up(h_size-1);
	}

# 删除元素

先将根元素与最后一个元素交换，再删去根元素。随后执行下沉的堆化操作。复杂度 $O(\log n)$ .