likes
comments
collection
share

用 JavaScript 实现优先队列和堆

作者站长头像
站长
· 阅读数 25

优先队列并不神秘，可以把它看成队列的一个升级版，即有优先级的队列。队列常用的例子是顾客去超市排队买单，那么优先队列就是老人可以优先买单。这里是根据人的年龄大小排，当然，我们也可以按照其他的条件排。当然，如果优先队列的每个元素有同样的优先级，那么就退化成了普通的队列。

优先队有两个特征：

  • 最高优先级的总是先出队
  • 同样优先级的遵循先进先出（First In - First Out）

为什么要使用优先队列？

我们可能会在下面的场景中碰到优先队列的应用：

  • 制定任务的时候，给任务排优先级：一级任务、二级任务……
  • 根据优先级执行系统任务的任务调度器
  • 一些算法：数据压缩（赫夫曼编码算法）、最短路径算法（Dijkstra 算法）、最小生成树算法（Prim 算法）
  • LeetCode 中的一些排序问题：查找第 k 个最小元素

这里有一些优先队列的非官方实现：

实现优先队列

JavaScript 标准没有提供一个可以给我们直接使用的实现。我们可以处于学习的角度，自己实现一个。优先队列有两个关键的操作：

  • 入队：在队列中插入元素
  • 出队：删除队列中的元素，按照它们插入的顺序

优先队列通常有一个比较函数。因为我们的数据可以是简单的，比如由数字组成的同样优先级的数组，也可以是复杂的，比如一个包含学生的各种信息的对象。这个比较函数可以定义我们使用何种优先顺序去排列。比如：

const pq= new PriorityQueue((x, y) => y.age - x.age);
pq.enqueue({ name: 'Maria', age: 23 });
pq.enqueue({ name: 'Nushi', age: 42 });
pq.enqueue({ name: 'Jose', age: 32 });

pq.dequeue(); // { name: 'Nushi', age: 42 }
pq.dequeue(); // { name: 'Jose', age: 32 }
pq.dequeue(); // { name: 'Maria', age: 23 }

我们可以传入一个比较函数，它要求按照年龄大小创建队列，年龄大的先出队。这就是最大堆，我们也可以修改比较函数创建最小堆：

const pq= new PriorityQueue((x, y) => x.age - y.age);

方法一、简单版：使用数组和排序算法实现

我们可以使用数组或者链表实现队列，优先队列需要增加一个纬度：按照优先级排列元素。

入队

每次插入一个新的元素，然后把这个元素按照优先级排序。它的复杂度如下：

  • 时间复杂度：O(n log n)，插入数组是常数时间，但是排序需要花费 O(n log n)。sort() 方法的时间复杂度是 O(n log n)。
  • 空间复杂度：O(n)，需要的空间随着入队的元素增加
class NaivePQ {
	constructor(comparator = (a, b) => a - b) {
		this.array = [];
		this.comparator = comparator;
	}

	// 插入元素
	add(value) {
		this.array.push(value);
		this.array.sort(this.comparator);
	}
}

出队

出队是从优先队列中移除一个元素。我们需要将优先级最高的元素移除并返回它的值。最高优先级的元素是第一个元素，因此，它的时间复杂度是 O(1)，但是我们还需要把剩余的元素重新排序，把移除的元素的位置填上新的高优先级的元素。因此它的时间复杂度是 O(n)。

// 从头删除元素，如果堆为空则返回 null
remove() {
    if (!this.size) return null;
    const value = this.array.shift();
    return value;
}

方法二：改进版：堆实现

从上面的简单版可以看到，我们删除元素的时间复杂度是 O(n)，能够再改进一些呢？当然可以，使用堆就可以做到。

堆是一种数据结构，根的元素的终是是最大（或最小）。因此有最大堆、最小堆。它有两个最基本的操作：插入元素和删除元素。通常来说，堆是一种完全二叉树，有以下特性：

  • 对于最小堆来说，父节点应该小于或等于子节点。最大堆则是：父节点大于或等于子节点。
  • 二叉树应该是完全二叉树。所有层都应该被填满，只有最后一层可能是空的，而且需要从左往右填满元素，不能有空位。

用 JavaScript 实现优先队列和堆

我们可以使用数组来表示堆，第一个元素是 root 节点，其余的是子节点。

用 JavaScript 实现优先队列和堆

我们可以根据当前节点的位置，得到它的父节点、左右节点的位置：

const parent = (i) => Math.ceil(i / 2 - 1);
const leftChild = (i) => 2 * i + 1;
const rightChild = (i) => 2 * i + 2;

入队

在堆中插入节点的步骤如下：

  1. 在尾部添加插入的节点
  2. 从当前位置（数组长度 - 1）一直向上冒泡（bubble up）到合适的位置，必须保证最大堆（或最小堆）的特性，即父节点大于等于（或小于等于）子节点。如果不符合这个特性，则通过比较当前节点的父节点和子节点的值，将该节点放在正确的位置。直到所有节点都符合最大堆（或最小堆）的特性为止。
class Heap {
	//  comparator 默认按照从小到大的顺序，即创建最小堆
	constructor(comparator = (a, b) => a - b) {
		this.array = [];
		this.comparator = (i1, i2) => comparator(this.array[i1], this.array[i2]);
	}

	get size() {
		return this.array.length;
	}

	swap(a, b) {
		[this.array[a], this.array[b]] = [this.array[b], this.array[a]];
	}

    // 插入新的节点
	add(value) {
		this.array.push(value);
		this.bubbleUp();
	}

	// 如果新的节点不符合优先级的顺序，则移动它，直到符合为止
	bubbleUp() {
		let curr = this.size - 1;
		const parent = (i) => Math.ceil(i / 2 - 1);
		// 比较父节点和当前节点（新节点）的优先级，
        // 低的排在上面，因此如果父节点比子节点优先级高，则交换两个节点，直到当前节点的优先级有序为止
		while (parent(curr) >= 0 && this.comparator(parent(curr), curr) > 0) {
			this.swap(parent(curr), curr);
			curr = parent(curr);
		}
	}
}

堆排序的时间复杂度是 O(log n)，这是新元素上浮需要交换的最大数。空间复杂度不变，依然是 O(n)。

出队

优先队列出队操作是删除优先级最高的元素。步骤如下：

  1. 从 root 移除一个元素。
  2. 因为 root 的位置空缺了，需要新的、有最大优先级的元素补位。我们可以把最后一个子节点和要移除 root 元素换个位置，然后把子节点根据优先级重新排序。这个过程即下浮（bubbleDown）或堆化（heapify）。

复杂度如下：

  • 时间复杂度：O(log n)，需要交换的最大数，即二叉树的高度。
  • 空间复杂度：O(n)
	// 删除节点
	remove(index = 0) {
		// 将要移除的节点和最后一个子节点交换
		this.swap(this.size - 1, index);
		// 移除节点并保存值
		const value = this.array.pop();
		// 使子节点按照优先级排序
		this.bubbleDown();
		return value;
	}

	bubbleDown(index = 0) {
		let curr = index;
		const left = (i) => 2 * i + 1;
		const right = (i) => 2 * i + 2;
		// 比较两个子节点的优先级，选出优先级最低的
		const getTopChild = (i) =>
			right(i) < this.size && this.comparator(left(i), right(i)) > 0
				? right(i)
				: left(i);

		// 比较父节点和选出的低优先级子节点，
		// 如果当前节点的优先级高，则交换两个节点，直到每个节点都优先级都有序为止
		while (
			left(curr) < this.size &&
			this.comparator(curr, getTopChild(curr)) > 0
		) {
			const next = getTopChild(curr);
			this.swap(curr, next);
			curr = next;
		}
	}

最大堆和最小堆

根据上面实现的优先队列，我们就可以传入不同的比较函数 comparator 来实现最大堆和最小堆了。

// 最大堆
class MinHeap extends Heap {
	constructor() {
		super((a, b) => a - b);
	}
}

// 最小堆
class MaxHeap extends Heap {
	constructor() {
		super((a, b) => b - a);
	}
}

完整实现

class Heap {
	//  comparator 默认按照从小到大的顺序
	constructor(comparator = (a, b) => a - b) {
		this.array = [];
		this.comparator = (i1, i2) => comparator(this.array[i1], this.array[i2]);
	}

	get size() {
		return this.array.length;
	}

	swap(a, b) {
		[this.array[a], this.array[b]] = [this.array[b], this.array[a]];
	}

	// 插入新的节点
	add(value) {
		this.array.push(value);
		this.bubbleUp();
	}

	// 如果新的节点不符合优先级的顺序，则移动它，直到符合为止
	bubbleUp() {
		let curr = this.size - 1;
		const parent = (i) => Math.ceil(i / 2 - 1);
		// 比较父节点和当前节点（新节点）的优先级，
                // 低的排在上面，因此如果父节点比子节点优先级高，则交换两个节点，直到当前节点的优先级有序为止
		while (parent(curr) >= 0 && this.comparator(parent(curr), curr) > 0) {
			this.swap(parent(curr), curr);
			curr = parent(curr);
		}
	}

	// 删除节点
	remove(index = 0) {
		// 将要移除的节点和最后一个子节点交换
		this.swap(this.size - 1, index);
		// 移除节点并保存值
		const value = this.array.pop();
		// 使子节点按照优先级排序
		this.bubbleDown();
		return value;
	}

	bubbleDown(index = 0) {
		let curr = index;
		const left = (i) => 2 * i + 1;
		const right = (i) => 2 * i + 2;
		// 比较两个子节点的优先级，选出优先级最低的
		const getTopChild = (i) =>
			right(i) < this.size && this.comparator(left(i), right(i)) > 0
				? right(i)
				: left(i);

		// 比较父节点和选出的低优先级子节点，
		// 如果当前节点的优先级高，则交换两个节点，直到每个节点都优先级都有序为止
		while (
			left(curr) < this.size &&
			this.comparator(curr, getTopChild(curr)) > 0
		) {
			const next = getTopChild(curr);
			this.swap(curr, next);
			curr = next;
		}
	}
}

class MinHeap extends Heap {
	constructor() {
		super((a, b) => a - b);
	}
}

class MaxHeap extends Heap {
	constructor() {
		super((a, b) => b - a);
	}
}

const pq = new MaxHeap((x, y) => x.age - y.age);
pq.add({ name: "Maria", age: 23 });
pq.add({ name: "Nushi", age: 42 });
pq.add({ name: "Jose", age: 32 });

console.log(pq.remove()); // { name: 'Nushi', age: 42 }
console.log(pq.array); // [{ name: 'Jose', age: 32 }, { name: 'Maria', age: 23 }]

应用

239. 滑动窗口最大值

总结

我们实现了一个优先队列，用堆改善了它的时间复杂度，并且基于这个优先队列，实现了最大堆和最小堆。它的时间复杂度是 O(log n)， 空间复杂度是 O(n)。

参考资料

array-sort.tq

Priority Queue Data Structure and Heaps Implemented in JavaScript

优先队列知识