桂园精品网站建设费用,wix网站制作,网站封面怎么做,阿里巴巴开网店的详细步骤如果对前端八股文感兴趣#xff0c;可以留意公重号#xff1a;码农补给站#xff0c;总有你要的干货。 今天分享一个非常热门的算法--堆排序。堆的运用非常的广泛#xff0c;例如#xff0c;Python中的heapq模块提供了堆排序算法#xff0c;可以用于实现优先队列#xf…如果对前端八股文感兴趣可以留意公重号码农补给站总有你要的干货。 今天分享一个非常热门的算法--堆排序。堆的运用非常的广泛例如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 来源稀土掘金 著作权归作者所有。商业转载请联系作者获得授权非商业转载请注明出处。
