堆

时游大约 9 分钟

堆

堆是一种满足特定条件的完全二叉树，主要分为两种类型：

小顶堆：任意节点值 ≤ 其子节点的值
大顶堆：任意节点值 ≥ 其子节点的值

堆作为完全二叉树的一个特例，具有以下特性：

最底层节点靠左填充，其他层节点都被填满。
二叉树的根节点称为“堆顶”，底层靠右的节点称为“堆底”。
对于大顶堆（小顶堆），堆顶元素（根节点）的值是最大（最小）的。

堆的常见操作

堆通常用于实现优先队列，大顶堆相当于元素按从大到小的顺序出队的优先队列。

堆的实现

想将大顶堆转为小顶堆，只需将所有大小逻辑取逆即可。

1. 堆的存储与表示

完全二叉树非常适合使用数组来进行表示，在使用数组表示完全二叉树时，索引代表节点在二叉树的位置。节点指针通过索引映射公式来实现：

索引映射公式：给定索引 i，其左子节点的索引为 2i+1，右子节点的索引为 2i+2，父节点的索引为(i-1)/2。当索引越界时，表示空节点或节点不存在。

/* 获取左子节点索引 */
const getLeftIndex = (i) => i * 2 + 1;

/* 获取右子节点索引 */
const getRightIndex = (i) => i * 2 + 2;

/* 获取父节点索引 */
const getParentIndex = (i) => Math.floor((i - 1) / 2);

2.访问堆顶元素

堆顶元素即为二叉树根节点，就是列表首个元素

3.元素入堆

给顶元素 val，先将其添加到堆底，添加后 val 可能大于堆中其他元素，不符合堆的成立条件，因此需要修复从插入节点到根节点的路径上的多个节点，这个操作被称为堆化。考虑从入堆节点开始，从底至顶执行堆化。我们比较插入节点与其父节点的值，如果插入节点更大，则将它们交换。然后继续执行此操作，从底至顶修复堆中的各个节点，直至越过根节点或遇到无须交换的节点时结束。

元素入堆步骤-1 元素入堆步骤-2 元素入堆步骤-3 元素入堆步骤-4 元素入堆步骤-5 元素入堆步骤-6 元素入堆步骤-7 元素入堆步骤-8 元素入堆步骤-9

const maxHeap = [];

/* 获取左子节点索引 */
const getLeftIndex = (i) => i * 2 + 1;
/* 获取右子节点索引 */
const getRightIndex = (i) => i * 2 + 2;

/* 获取父节点索引 */
const getParentIndex = (i) => Math.floor((i - 1) / 2);

/* 获取堆顶元素 */
const peek = () => maxHeap[0];

/* 获取大小 */
const size = () => maxHeap.length;

/* 元素入堆 */
const push = (val) => {
	maxHeap.push(val);
	// 开始堆化
	shiftUp(size() - 1);
};

/* 交换元素 */
const swap = (i, p) => {
	[maxHeap[i], maxHeap[p]] = [maxHeap[p], maxHeap[i]];
};

// 堆化
const shiftUp = (i) => {
	while (true) {
		// 查找parent与其对比
		const p = getParentIndex(i);
		// 当前元素小于父节点，满足堆条件
		if (maxHeap[i] <= maxHeap[p]) break;

		// 否则交换
		swap(i, p);
		// 循环向上堆化
		i = p;
	}
};

4. 堆顶元素出堆

堆顶元素是二叉树的根节点，如果直接删除首元素，那么二叉树的其余节点的索引都会发生变化，这会使得继续堆化修复变得困难，为此进行以下操作：

交换堆顶元素与堆底元素
交换完成后删除堆底元素
从根节点开始，从顶至底进行堆化操作

从顶到底进行堆化操作跟从底到顶进行堆化操作区别在于，从顶到底堆化时，将根节点与其子节点值进行对比，将最大的子节点与其交换，循环执行该操作，直到越过叶节点或遇到无需交换的节点为止。

堆顶元素出堆步骤 - 1 堆顶元素出堆步骤 - 2 堆顶元素出堆步骤 - 3 堆顶元素出堆步骤 - 4 堆顶元素出堆步骤 - 5 堆顶元素出堆步骤 - 6 堆顶元素出堆步骤 - 7 堆顶元素出堆步骤 - 8 堆顶元素出堆步骤 - 9 堆顶元素出堆步骤 - 10


// 从顶到底进行堆化
const shiftDown = (i) => {
	while (true) {
		// 元素本身、左子节点、右子节点对比
		const l = getLeftIndex(i),
			r = getRightIndex(i);

		let ma = l; // 设置ma为三个中最大值
		if (l < size() && maxHeap[l] > maxHeap[i]) ma = l;
		if (i < size() && maxHeap[r] > maxHeap[ma]) ma = r;

		// 无需堆化，直接跳出
		if (ma === i) break;

		// 交换当前节点与子节点最大
		swap(i, ma);

		// 继续向下堆化
		i = ma;
	}
};

堆的常见应用

优先队列：堆通常作为实现优先队列的首选数据结构，其入队和出队操作时间复杂度均为O(logn)，而建队操作为O(n)。
堆排序：给定一组数据，可以将其建堆，然后不断进行元素的出堆操作，从而得到有序数据。
获取最大的K个元素：经典算法问题。

建堆操作

在某些情况下，我们希望使用一个列表的所有元素来构建一个堆，这个过程被称为“建堆操作”。

借助入堆操作实现

首先创建一个空堆，然后遍历列表，依次对每个元素执行“入堆操作”，即将元素添加到堆底，再对该元素执行“从底至顶”堆化。

每当一个元素入堆时，堆的长度加一。由于节点是从顶到底依次被添加到二叉树的，因此堆是“自上而下”构建的。

设元素数量为n，每个元素的入堆操作使用时间为O(logn)，因此建堆操作的时间复杂度为O(nlogn)。

通过遍历堆化实现

更高效的建堆方法：

将列表中所有节点原封不动添加到堆中，此时并不构成形成堆的条件。
倒序遍历堆，依次对每个非叶节点执行“从顶至底”堆化操作。

每当堆化一个节点后，以该节点为根节点的子树就形成了一个合法的堆。

复杂度分析

假设完美二叉树的节点数量为n，则叶节点数量为(n+1)/2，向下取整，因此需要堆化的节点数量为(n-1)/2。高度为h的完美二叉树节点数量为n = 2^(h+1) - 1，时间复杂度为O(n)。

Top-k问题

给定一个长度为n的无序数组nums，请返回数组中最大的k个元素。

方法一：遍历选择

我们可以对列表进行k轮遍历，依次提取第1、2、3、...、k个最大元素，时间复杂度为O(nk)。此时只适合k << n的情况因为当k与n比较接近时，时间复杂度趋近与O(n^2)，非常耗时。

当k = n时，就相当于对数组进行排序，此时等价于“选择排序”算法。

方法二：排序

可以先对数组nums进行排序，再返回最右边的k个元素，时间复杂度为O(nlogn)。

方法三：堆

我们可以基于堆更高效解决Top-k问题，具体如下：

先初始化一个小顶堆，其堆顶元素最小。
先将数组的前k项元素依次入堆。
从第k+1元素开始，若当前元素大于堆顶元素，则将堆顶元素出堆，并将当前元素入堆。
遍历完数组nums后，堆中保存的就是最大的k个元素。

基于堆寻找最大的 k 个元素 - 1 基于堆寻找最大的 k 个元素 - 2 基于堆寻找最大的 k 个元素 - 3 基于堆寻找最大的 k 个元素 - 4 基于堆寻找最大的 k 个元素 - 5 基于堆寻找最大的 k 个元素 - 6 基于堆寻找最大的 k 个元素 - 7 基于堆寻找最大的 k 个元素 - 8 基于堆寻找最大的 k 个元素 - 9

总共执行了n轮入堆和出堆，堆的最大长度为k，因此时间复杂度为O(n logk)，效率非常高，当k较小时趋近于O(n)，当k较大时，时间复杂度不超过O(nlogn)。

/**
 * Top-k问题
 */

let nums = [1, 7, 6, 3, 2];
let k = 3; // 获取数组中最大的k个元素

// 方法一：k轮遍历
function topKMap(nums, k) {
	let result = [];
	let copy = JSON.parse(JSON.stringify(nums));

	for (let i = 0; i < k; i++) {
		// 将数组中最大push进去, 并在数组中删除
		result.push(Math.max(...copy));
		copy.splice(copy.indexOf(Math.max(...copy)), 1);
	}

	console.log(result);
	return result;
}

topKMap(nums, k);

// 方法二：排序
function topKSort(nums, k) {
	let result = [];
	let copy = JSON.parse(JSON.stringify(nums));

	// 从大到小排序
	copy.sort((a, b) => b - a);

	// 取0~k索引位置元素
	result = copy.slice(0, k);

	console.log(result);
	return result;
}

topKSort(nums, k);

// 方法三：堆
class MaxHeap {
	heap;

	constructor(heap) {
		this.heap = heap || []; // 初始化堆
	}

	/* 获取左子节点索引 */
	getLeftIndex = (i) => i * 2 + 1;

	/* 获取右子节点索引 */
	getRightIndex = (i) => i * 2 + 2;

	/* 获取父节点索引 */
	getParentIndex = (i) => Math.floor((i - 1) / 2);

	/* 获取堆顶元素 */
	peek = () => this.heap[0];

	/* 获取大小 */
	size = () => this.heap.length;

	/* 堆化 */
	shiftUp = (i) => {
		while (true) {
			// 当前节点小于父节点，则交换
			if (this.heap[i] <= this.heap[this.getParentIndex(i)]) {
				// 交换
				this.swap(i, this.getParentIndex(i));
				// 继续向上堆化
				i = this.getParentIndex(i);
			} else {
				break;
			}
		}
	};

	/* 元素入堆 */
	push = (val) => {
		this.heap.push(val);
		// 开始堆化
		this.shiftUp(this.size() - 1);
	};

	/* 交换元素 */
	swap = (i, p) => {
		[this.heap[i], this.heap[p]] = [this.heap[p], this.heap[i]];
	};

	// 堆顶出堆
	pop = () => {
		if (this.heap.length === 0) return "堆为空";

		// 交换堆顶与堆底元素
		this.swap(0, this.size() - 1);

		// 删除堆底元素（原堆顶元素）
		this.heap.pop();
	};
}

function topKHeap(nums, k) {
	let heap = new MaxHeap([]);
	// 将前k项入堆
	for (let i = 0; i < k; i++) {
		// 1 7 6 建堆
		heap.push(nums[i]);
	}
	// 从k+1项开始，若当前元素大于堆顶元素，则堆顶元素出堆，该元素入堆
	for (let j = k; j < nums.length; j++) {
		if (nums[j] > heap.peek()) {
			// 堆顶出堆
			heap.pop();
			// 该元素入堆
			heap.push(nums[j]);
		}
	}

	console.log(heap.heap);
}

topKHeap(nums, k);

堆

# 堆

# 堆

# 堆的常见操作

# 堆的实现

# 1. 堆的存储与表示

# 2.访问堆顶元素

# 3.元素入堆

# 4. 堆顶元素出堆

# 堆的常见应用

# 建堆操作

# 借助入堆操作实现

# 通过遍历堆化实现

# 复杂度分析

# Top-k问题

# 方法一：遍历选择

# 方法二：排序

# 方法三：堆

堆

堆