前端算法面试之堆排序-每日一练

如果对前端八股文感兴趣，可以留意公重号：码农补给站，总有你要的干货。

今天分享一个非常热门的算法--堆排序。堆的运用非常的广泛，例如，Python中的heapq模块提供了堆排序算法，可以用于实现优先队列；Java中的PriorityQueue类实现了堆队列，可以用于实现优先级任务队列；C++中的优先队列容器适配器提供了基于堆的优先队列实现。

还有前端开发特别熟悉的React框架中也用到了，其中使用堆来管理组件的渲染优先级。在React中，组件的渲染优先级被抽象为一种堆结构，称为“Fiber堆”。Fiber堆中的每个节点代表一个组件，组件的优先级越高，在渲染时越优先。

什么是堆呢？

堆分为大根堆和小根堆，大根堆的每个结点的值都大于等于其子结点的值，即该结点是该子树中的最大值。小根堆的每个结点的值都小于等于其子结点的值，即该结点是该子树中的最小值。

他们都是一种特殊的完全二叉树，物理存储结构一般是一个连续的线性数组。并且节点的下标和左右子节点的下标之间存在一定的关系。假设节点的下标为 i，那么它的左子节点的下标为 2i，右子节点的下标为 2i + 1。相反地，如果一个节点的下标为 j，那么它的父节点的下标为 j/2（向下取整）。

那如何利用堆进行排序呢

以大根堆为例，就两步，建堆和堆化。

第一步先建堆，然后将堆顶和数组的最后一位更换位置，数组的最后一个位置就是最大值了。堆的大小减一。

第二步，再调整堆，使其再次满足大根堆的定义。

重复上面两步，直到堆的大小为1。

下面用代码实现这两个过程

建堆

class Heap {
	constructor(data) {
		this.data = data;
	}
 
	build() {
		for (let i = 2; i < this.data.length; i++) {
			this.heapfyTop(i);
		}
	}
 
	heapfyTop(n) {
		while (n > 1 && this.data[n] > this.data[Math.floor(n / 2)]) {
			this.swap(n, Math.floor(n / 2));
			n = Math.floor(n / 2);
		}
	}
 
	swap(index1, index2) {
		const temp = this.data[index1];
		this.data[index1] = this.data[index2];
		this.data[index2] = temp;
	}
}

建堆有两种方法，这里先讲第一种。

建堆的过程有点像插入排序，假设第一个元素已经是一个大根堆，从第二个节点开始往后遍历，每个元素都往前面的大根堆中插入。直到遍历完整个数组的元素。完整的大根堆就建好了。

假设往大根堆中插入元素a，先将元素a放到数组的最后一个位置，然后比较a元素和其父元素的大小，如果大于父元素，就将两个元素的位置更换。这样a元素就有了新的父元素。然后继续比较a 元素和其父元素的大小。直到a元素小于等于父元素，或者a元素变成了大根堆的堆顶。

这个比较的过程，就是大根堆堆化的过程

上面代码中，build函数作用是从数组的第二个元素开始往后遍历，每遍历一个元素，就调用一次heapfyTop 函数。heapfyTop 函数的作用是调整大根堆。遍历完整个数组，堆也就建好了。

数组元素从下标 1 开始

测试代码

const data = [-1, 21, 33, 5, 42, 123, 54, 65, 23, 33, 55];
const heap = new Heap(data);
 
heap.build();
 
console.log(heap.data);
// [
//   -1, 123, 55, 65, 33,
//   42,   5, 54, 21, 23,
//   33
// ]

新建一个 Heap 类，然后调用 build 方法，并且将堆的内容打印出来。打印数组确实满足大根堆定义，没有问题。

堆排序

class Heap {
 
  //省略其他代码
  sort() {
    this.build2(); // 构建大顶堆
    let len = this.data.length - 1; // 数组长度减1，因为堆排序是从下标1开始
    while (len > 1) { // 当堆长度大于1时，继续排序
      this.swap(1, len); // 交换堆顶元素与堆尾元素
      len--; // 减小堆长度
      this.heapfyBelow(1, len); // 对新的堆顶元素进行调整
    }
  }
 
  heapfyBelow(n, end) { // 对下标为n的元素进行调整，使其满足大顶堆的性质，end为调整范围的上界
    // 是否是叶子节点
    while (n * 2 <= end) {
      let maxIndex = n; // 假设当前结点是最大值
      // 如果有左孩子，且左孩子的值比当前结点大，则将maxIndex更新为左孩子的下标
      if (n * 2 <= end && this.data[maxIndex] < this.data[n * 2]) maxIndex = n * 2;
      // 如果有右孩子，且右孩子的值比当前结点大，则将maxIndex更新为右孩子的下标
      if (n * 2 + 1 <= end && this.data[maxIndex] < this.data[n * 2 + 1]) maxIndex = n * 2 + 1;
      // 如果maxIndex没有发生变化，说明当前结点的值已经是最大值，调整结束
      if (maxIndex == n) break;
      // 否则，交换当前结点与maxIndex指向的结点
      this.swap(n, maxIndex);
      n = maxIndex; // 更新当前结点为新的maxIndex
    }
  }
 
}

将堆顶元素和最后一个元素更换位置之后，堆的大小减一，并且需要重新调整堆的大小，所以代码中 len--，并且调用了this.heapfyBelow(1, len)。这也是一个堆调整的代码，与之前不同的是，这个代码是从上往下调整堆。不断地比较当前元素和子元素，如果有子元素比当前元素还大的，就更换位置。直到遍历到叶子节点，或者没有比当前元素更大的子节点。

为了方便调用者，sort 函数中直接调用了 build 函数，完成建堆的步骤。

测试代码

const data = [-1, 21, 33, 5, 42, 123, 54, 65, 23, 33, 55];
const heap = new Heap(data);
heap.sort();
console.log(heap.data);
// [
//    -1,  5, 21, 23, 33,
//    33, 42, 54, 55, 65,
//   123
// ]

打印的数组有序，代码正确

完整代码

class Heap {
	constructor(data) {
		this.data = data;
	}
 
	build() {
		for (let i = 2; i < this.data.length; i++) {
			this.heapfyTop(i);
		}
	}
 
	sort() {
		this.build2();
		let len = this.data.length - 1;
		while (len > 1) {
			this.swap(1, len);
			len--;
			this.heapfyBelow(1, len);
		}
	}
 
	heapfyBelow(n, end) {
		// 是否是叶子节点
		while (n * 2 <= end) {
			let maxIndex = n;
			// 是否有左孩子
			if (n * 2 <= end && this.data[maxIndex] < this.data[n * 2]) maxIndex = n * 2;
			// 是否有右孩子
			if (n * 2 + 1 <= end && this.data[maxIndex] < this.data[n * 2 + 1]) maxIndex = n * 2 + 1;
			if (maxIndex == n) break;
			this.swap(n, maxIndex);
			n = maxIndex;
		}
	}
  
	heapfyTop(n) {
		while (n > 1 && this.data[n] > this.data[Math.floor(n / 2)]) {
			this.swap(n, Math.floor(n / 2));
			n = Math.floor(n / 2);
		}
	}
  
	swap(index1, index2) {
		const temp = this.data[index1];
		this.data[index1] = this.data[index2];
		this.data[index2] = temp;
	}
}
 
const data = [-1, 21, 33, 5, 42, 123, 54, 65, 23, 33, 55];
const heap = new Heap(data);
 
heap.sort();
 
console.log(heap.data);

这是堆排序的完整代码，大家可以直接 copy 下来在本地跑一跑

总结

这篇文章分享了堆排序的概念讲解以及 JS 代码实现。堆排序是一种高效的排序算法，利用堆的特性进行排序。它的时间复杂度为O(nlogn)，通过建堆和堆化的过程，可以将一个无序的数组转化为有序的数组。堆排序在实际应用中有广泛的应用，特别是在需要维护优先级队列的场景中非常有用。

下篇文章来分享建堆的另一种方式，以及堆的元素如何删除，并且分析堆排序的时间复杂度

作者：慢功夫
链接：https://juejin.cn/post/7300779513910132747
来源：稀土掘金
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。