Heap

Heap

堆/大根堆：每个节点包含一个键、且大于等于其子女键、基本完备 的二叉树

• 认为非叶子节点自动满足大于其子女键值
• 根到某个叶子节点路径上，键值序列递减（允许键值相等则是 非递增）
• 键值之间没有从左到右的次序，即树的同一层节点间没有任何 关系，或者说左右子树之间没有任何关系

堆特性

• 完全二叉树特性参见完全二叉树
• 堆的根总是包含了堆的最大元素
• 堆的节点及该节点子孙也是一个堆

• 堆这种数据结构经常被用于实现优先队列

最小堆

min-heap：（最大）堆的镜像

• 堆的主要特性最小堆也满足，但
  • 最小堆根节点包含最小元素
• 可通过给元素取反构造（最大）堆得到最小堆

堆算法

Bottom-Up Heap Construction

自底向上堆构造：先利用所有元素构造二叉树，从倒数第二层开始 修改使得整棵树满足堆要求

算法

• 将给定线性表对应为（初始化）一棵完全二叉树
• 对二叉树进行堆化，从最后父母节点开始、到根为止，算法检查 节点键是否满足大于等于其子女键
  • 若不满足，交换节点键K和其子女最大键值
  • 在新位置上检查是否满足大于子女键值，直到满足为止
• 对以当前节点为根的子树满足堆化条件后，算法对节点直接前趋 进行检查，直到树根满足堆化

HeapAdjust(H[0..n-1], cur):
	// 左右子树已经为堆，仅根节点元素不一定满足
	// 输入：待调整堆H、根节点cur，cur左右子树已经为堆
	// 输入：调整后堆
	while 2*cur+2 < n:

		// 获取左右子女中最大者
		if 2*cur+2 < n:
			_tmp = argmax(H[2*cur+1], H[2*cur+2])
		else:
			_tmp = 2*cur+1

		// 交换自身和最大子女
		if H[_tmp] > H[cur]:
			swap(H[cur], H[_tmp])
			cur = _tmp
		else:
			// 从底向上建堆，左、右子树均为堆
			// 则此时已经满足堆性质
			break

	return H

HeapBottomUp(H[0..n-1]):
	// 用自底向上算法，从给定数组元素中构造一个堆
	// 输入：可排序数组H[0..n-1]
	// 输出：堆H[0..n-1]
	for i=floor((n-1)/2) to 0:
		HeapAdjust(H, i)
	return H

算法特点

• 算法效率
  • 时间效率：最差情况，每个位于树第i层节点会移到叶子层 h中，每次移动比较两次，则总键值比较次数 $C_{worst}=2(n-log_2(n+1))$ （将各层叶子节点可能交换次数加总即差比数列求和）

Top-Down Heap Construction

自顶向下堆构造算法：先利用部分元素构建堆顶，把新键连续插入 已经构造好的堆末尾，修改使之满足堆要求

算法

• 把包含键K的新节点附加在当前堆最后一个叶子节点
• 将K与其父母进行比较
  • 若后者大于K，算法停止
  • 否则交换这两个键，并比较K和其新父母，直到K不大于其 父母或是达到了树根

算法特点

• 算法效率
  • 操作所需键值比较次数小于堆高度$h \approx log_2 n$， 则总比较次数$\in \Theta(nlogn)$

删除堆根节点

算法

• 根键和堆中最后一个键K交换
• 堆规模减1（删除原根键）
• 按照自底向上堆构造算法，把K沿着树向下筛选使得新树满足 堆化

算法特点

• 算法效率
  • 效率取决于树堆化所需比较次数，不可能超过树高度两倍， 即$\in O(logn)$

堆排序算法

算法

• 为给定数组构造堆
• 删除最大键，即对堆应用n-1此根删除操作

算法特点

• 算法效率

  • 根删除阶段算法所需比较次数

    $$\begin{align} C(n) & \leq 2\sum_{i=1}^{n-1} \lfloor log_2i \rfloor \\ & \leq 2 \sum_{i=1}^{n-1} log_2(n-1) \\ & = 2(n-1)log_2(n-1) \end{align}$$

  • 两阶段总效率$\in O(nlogn)$

  • 详细分析证明，无论最差情况、平均情况下，时间效率 $\in \Theta(nlogn)$

• 堆排序时间效率和归并排序、快排时间效率属于同一类，但是 堆排序是在位的（不需要额外存储空间）

• 随机实验表明：堆排序比快排慢、和归并排序相比有竞争力