Skip to content

二叉堆

2021-06-05

简介

二叉堆(Binary Heap)是一种基于完全二叉树的数据结构。

  • 小根堆:任意节点 其父节点,根节点最小;
  • 大根堆:任意节点 其父节点,根节点最大。

本篇以小根堆为例,介绍二叉堆的实现方式。

构造

按照从上到下,从左到右的顺序给节点编号。

该二叉堆具有以下性质:

  • 1 号节点是根节点;
  • u 号的父节点为 u2(向下取整);
  • u 号的左子节点为 2u,右子节点为 2u+1
  • 二叉堆的任意一条支路都按照升序排序。

使用数组保存二叉堆。

cpp
int t[], n;
// t[u] : u 号节点的值
// n : 节点总数

插入

如何往小根堆中插入元素 2

  1. 在堆底新建节点,值为 2
  2. 对新节点所在支路进行排序.重复执行以下步骤。
    • 若新节点 < 其父节点,则交换它们的位置,否则跳出循环。

时间复杂度为 O(nlogn)

cpp
// 插入元素 val
void push(int val) {
	t[++ n] = val; // 新建节点
	for (int u = n; u != 1; u /= 2) {
		if (t[u] < t[u / 2])
			swap(t[u], t[u / 2]);
		else break;
	}
}

移除

将小根堆的根节点移除,如何调整使其仍为小根堆?

  1. 把堆底最后一个元素移到根节点;
  2. 从根节点 u=1 开始,重复执行以下步骤:
    • 比较 u 的两个子节点,取最小的一个,记为 v
    • t[u]>t[v],交换节点 uv 的位置,并使 u=v,否则跳出循环。

cpp
// 移除根节点
void pop() {
	t[1] = t[n --];
	for (int u = 1; 2 * u <= n; ) {
		int v = 2 * u;
		if (v + 1 <= n && t[v + 1] < t[v])
			v ++; // 取最小的子节点
		if (t[u] > t[v])
			swap(t[u], t[v]), u = v;
		else break;
	}
}

模板

cpp
int t[], n;

void push(int val) {
	t[++ n] = val;
	for (int u = n; u != 1; u /= 2) {
		if (t[u] < t[u / 2])
			swap(t[u], t[u / 2]);
		else break;
	}
}

void pop() {
	t[1] = t[n --];
	for (int u = 1; 2 * u <= n; ) {
		int v = 2 * u;
		if (v + 1 <= n && t[v + 1] < t[v])
			v ++;
		if (t[u] > t[v])
			swap(t[u], t[v]), u = v;
		else break;
	}
}