算法|最大堆、最小堆和堆排序的实现（JavaScript）

server/2024/9/23 3:24:15/

一些概念

  • 堆：特殊的完全二叉树，具有特定性质的完全二叉树。
  • 大根堆：父节点 > 子节点
  • 小根堆：父节点 < 子节点

二叉堆也属于完全二叉树，所以可以用数组表示。

  • 若下标从1开始，左节点为 2*i ，右节点为 2*i+1 ，父节点为 i//2 。
  • 若下标从1开始，左节点为 2*i+1 ，右节点为 2*i+1+2 ，父节点为 (i-1)//2 。
    image.png

最大堆

两个重要方法，插入元素和移出元素。

  • 插入元素：在堆尾插入元素，调用辅助方法，将该元素上浮到正确位置。
  • 移出元素：将堆尾元素删去并替换到堆首，将该元素下沉到正确位置。

解释：

  • 上浮：如果父节点更大，则替换，循环直至比父节点小。
  • 下沉：如果子节点中较大的那个更小，则替换，循环直至子节点都比自身小。

实现

javascript">class MaxHeap {constructor() {this.heap = []}isEmpty() {return this.heap.length === 0}size() {return this.heap.length}#getParentIndex(idx) {return Math.floor((idx-1)/2)}#getLeft(idx) {return idx * 2 + 1}#getRight(idx) {return idx * 2 + 2}// 插入insert(v) {this.heap.push(v)this.#swim(this.size()-1)}// 删除最大值deleteMax() {const max = this.heap[0]this.#swap(0, this.size() - 1) // 将根和最后一个元素交换this.heap.pop() // 防止对象游离this.#sink(0) // 下沉，恢复有序性return max}// 第i个是否小于第j个#compare(a, b) {return a < b}// 交换#swap(i, j) {[this.heap[i], this.heap[j]] = [this.heap[j], this.heap[i]]}// 上浮#swim(k) {let parent = this.#getParentIndex(k)while(k > 0 && this.#compare(this.heap[parent], this.heap[k])) {this.#swap(parent, k)k = parentparent = this.#getParentIndex(k)}}// 下沉#sink(k) {while (this.#getLeft(k) < this.size()) {let j = this.#getLeft(k)// j 指向子节点的较大值if (j+1 < this.size() && this.#compare(this.heap[j], this.heap[j+1])) j++// 如果子节点都小if (this.#compare(this.heap[j], this.heap[k])) breakthis.#swap(k, j)k = j}}
}

测试

javascript">const mh = new MaxHeap()
mh.insert(20)
mh.insert(80)
mh.insert(50)
mh.insert(40)
mh.insert(30)
mh.insert(40)
mh.insert(20)
mh.insert(10)
mh.insert(35)
mh.insert(15)
mh.insert(90)
console.log(mh.heap)
// [ <1 empty item>, 90, 80, 50, 35, 40, 40, 20, 10, 20, 15, 30 ]
mh.deleteMax()
mh.deleteMax()
mh.deleteMax()
console.log(mh.heap)
// [ <1 empty item>, 40, 35, 40, 20, 30, 15, 20, 10 ]

最小堆

与最小堆相比，仅是交换条件不同

实现

javascript">class MinHeap {constructor() {this.heap = []}isEmpty() {return this.heap.length === 0}size() {return this.heap.length}#getParentIndex(idx) {return Math.floor((idx-1)/2)}#getLeft(idx) {return idx * 2 + 1}#getRight(idx) {return idx * 2 + 2}// 插入insert(v) {this.heap.push(v)this.#swim(this.size()-1)}// 删除最大值deleteMin() {const max = this.heap[0]this.#swap(0, this.size() - 1) // 将根和最后一个元素交换this.heap.pop() // 防止对象游离this.#sink(0) // 下沉，恢复有序性return max}// 第i个是否小于第j个#compare(a, b) {return a > b}// 交换#swap(i, j) {[this.heap[i], this.heap[j]] = [this.heap[j], this.heap[i]]}// 上浮#swim(k) {let parent = this.#getParentIndex(k)while(k > 0 && this.#compare(this.heap[parent], this.heap[k])) {this.#swap(parent, k)k = parentparent = this.#getParentIndex(k)}}// 下沉#sink(k) {while (this.#getLeft(k) < this.size()) {let j = this.#getLeft(k)// j 指向子节点的较小值if (j+1 < this.size() && this.#compare(this.heap[j], this.heap[j+1])) j++// 如果子节点都大if (this.#compare(this.heap[j], this.heap[k])) breakthis.#swap(k, j)k = j}}
}

测试

javascript">const mh = new MinHeap()
mh.insert(20)
mh.insert(80)
mh.insert(50)
mh.insert(40)
mh.insert(30)
mh.insert(40)
mh.insert(20)
mh.insert(10)
mh.insert(35)
mh.insert(15)
mh.insert(90)
console.log(mh.heap)
// [10, 15, 20, 30, 20, 50, 40, 80, 35, 40, 90]
mh.deleteMin()
mh.deleteMin()
mh.deleteMin()
console.log(mh.heap)
// [20, 30, 40, 35, 40, 50, 90, 80]

堆（自定义比较函数）

默认为最大堆，根据元素的大小进行排序，可自定义排序规则，返回值为布尔值。

javascript">class Heap {constructor(compareFn) {this.heap = []this.compare = (typeof compareFn === 'function') ? compareFn : this.#defaultCompare}isEmpty() {return this.heap.length === 0}size() {return this.heap.length}#getParentIndex(idx) {return Math.floor((idx-1)/2)}#getLeft(idx) {return idx * 2 + 1}#getRight(idx) {return idx * 2 + 2}// 插入insert(v) {this.heap.push(v)this.#swim(this.size()-1)}// 删除最大值delete() {const max = this.heap[0]this.#swap(0, this.size() - 1) // 将根和最后一个元素交换this.heap.pop() // 防止对象游离this.#sink(0) // 下沉，恢复有序性return max}// 第i个是否小于第j个#defaultCompare(a, b) {return a < b}// 交换#swap(i, j) {[this.heap[i], this.heap[j]] = [this.heap[j], this.heap[i]]}// 上浮#swim(k) {let parent = this.#getParentIndex(k)while(k > 0 && this.compare(this.heap[parent], this.heap[k])) {this.#swap(parent, k)k = parentparent = this.#getParentIndex(k)}}// 下沉#sink(k) {while (this.#getLeft(k) < this.size()) {let j = this.#getLeft(k)// j 指向子节点的较大值if (j+1 < this.size() && this.compare(this.heap[j], this.heap[j+1])) j++// 如果子节点都小if (this.compare(this.heap[j], this.heap[k])) breakthis.#swap(k, j)k = j}}
}

测试

javascript">const mh = new Heap((a,b)=>a.val<b.val)
mh.insert({val: 20})
mh.insert({val: 45})
mh.insert({val: 56})
mh.insert({val: 12})
mh.insert({val: 93})
mh.insert({val: 34})
mh.insert({val: 12})
mh.insert({val: 84})
console.log(mh.heap)
// [
//   { val: 93 },
//   { val: 84 },
//   { val: 45 },
//   { val: 56 },
//   { val: 20 },
//   { val: 34 },
//   { val: 12 },
//   { val: 12 }
// ]
mh.delete()
mh.delete()
console.log(mh.heap)
// [
//   { val: 56 },
//   { val: 20 },
//   { val: 45 },
//   { val: 12 },
//   { val: 12 },
//   { val: 34 }
// ]

堆排序

（1）先原地创建一个最大堆，因为叶子节点没有子节点，因此只需要对非叶子节点从右向左进行下沉操作

（2）把堆首（堆的最大值）和堆尾替换位置，堆大小减一，保持非堆是递增的，保持数组最后一个元素是最大的，最后对堆首进行下沉操作（或者说把非堆重新堆化）。

（3）重复第二步直至清空堆。

注意：排序的数组第一个元素下标是 0 ，跟上面处理边界不一样。

实现

javascript">function heapSort (arr) {// arr = arr.slice(0) // 是否原地排序let N = arr.length - 1if (!arr instanceof Array) {return null}else if (arr instanceof Array && (N === 0 || N === -1) ) {return arr}function exch(i, j) {[arr[i], arr[j]] = [arr[j], arr[i]]}function less(i, j) {return arr[i] < arr[j]}function sink(k) {while (2 *k + 1 <= N) {let j = 2 * k + 1// j 指向子节点的较大值if (j+1 <= N && less(j, j+1)) {j++}// 如果子节点都小if (less(j, k)) breakexch(k, j)k = j}}// 构建堆for(let i = Math.floor(N/2); i >= 0; i--) {sink(i)}// 堆有序while (N > 0) {exch(0, N--)sink(0)}
}

另一个实现

javascript">function heapSort (arr) {// arr = arr.slice(0) // 是否原地排序let N = arr.lengthif (!arr instanceof Array) {return null}else if (arr instanceof Array && (N === 0 || N === -1) ) {return arr}function getParentIndex(idx) {return Math.floor((idx-1)/2)}function getLeft(idx) {return idx * 2 + 1}function getRight(idx) {return idx * 2 + 2}function swap(i, j) {[arr[i], arr[j]] = [arr[j], arr[i]]}function compare(i, j) {return i < j}function sink(k) {while (getLeft(k) < N) {let j = getLeft(k)// j 指向子节点的较大值if (j+1 < N && compare(arr[j], arr[j+1])) j++// 如果子节点都小if (compare(arr[j], arr[k])) breakswap(k, j)k = j}}// 构建堆for(let i = Math.floor(N/2); i >= 0; i--) {sink(i)}// 堆有序while (N > 1) {swap(0, --N)sink(0)}
}

测试

javascript">const arr1 = [15, 20, 30, 35, 20, 50, 40, 80, 10, 40, 90]
heapSort(arr1)
console.log(arr1)
// [10, 15, 20, 20, 30, 35, 40, 40, 50, 80, 90]
const arr2 = [62, 88, 58, 47, 35, 73, 51, 99, 37, 93];
heapSort(arr2)
console.log(arr2)
// [35, 37, 47, 51, 58, 62, 73, 88, 93, 99]

参考

  1. algs4
  2. 【JS手写最小堆（小顶堆）、最大堆（大顶堆）】：https://juejin.cn/post/7128369000001568798
  3. 【数据结构与算法(4)——优先队列和堆】：https://zhuanlan.zhihu.com/p/39615266
  4. 【最大堆最小堆及堆排序】：https://mingshan.fun/2019/05/14/heap/
  5. 【搞定JavaScript算法系列–堆排序】：https://juejin.cn/post/6844903830258188296

http://www.ppmy.cn/server/13988.html

相关文章

37. UE5 RPG创建自定义的Ability Task

37. UE5 RPG创建自定义的Ability Task

在前面的文章中&#xff0c;我们实现了一个火球术的一些基本功能&#xff0c;火球术技能的释放&#xff0c;在技能释放后&#xff0c;播放释放动画&#xff0c;在动画播放到需要释放火球术的位置时&#xff0c;将触发动画通知&#xff0c;在动画通知中触发标签事件&#xff0c;…
阅读更多...
SpringMVC基础篇（二）

SpringMVC基础篇（二）

文章目录 1.Postman1.基本介绍Postman是什么&#xff1f; 2.Postman快速入门1.Postman下载点击安装自动安装在系统盘 2.基本操作1.修改字体大小2.ctrl “” 放大页面3.进入创建请求界面 2.需求分析3.具体操作4.保存请求到文件夹中1.点击保存2.创建新的文件夹3.保存成功 3.使用…
阅读更多...
精度论文Generative Prompt Model for Weakly Supervised Object Localization

精度论文Generative Prompt Model for Weakly Supervised Object Localization

Generative Prompt Model for Weakly Supervised Object Localization 中国科学院大学&&浙江大学CVPR20231.Abstract 当从图像类别标签中学习对象定位模型时，弱监督对象定位(WSOL)仍然具有挑战性， 传统的鉴别训练激活模型的方法忽略了具有代表性但鉴别性较差的对象…
阅读更多...
JVM支持的可配置参数查看和分类

JVM支持的可配置参数查看和分类

JVM参数大致可以分为三类: 标注指令:-开头。 这些是所有的HotSpot都支持的参数。可以用java-help 打印出来。 非标准指令: -X开头。 这些指令通常是跟特定的HotSpot版本对应的。可以用java -X打印出来。 不稳定参数: -XX 开头。 这一类参数是跟特定HotSpot版本对应的&#x…
阅读更多...
面向对象设计与分析（41）建造者模式builder

面向对象设计与分析（41）建造者模式builder

文章目录 1 定义2 示例3 实际应用1 定义 看下builder模式的官方定义： The intent of the Builder design pattern is to separate the construction of a complex object from its representation. By doing so the same construction process can create different represe…
阅读更多...
CSAPP 第九章---虚拟内存

CSAPP 第九章---虚拟内存

1.为什么需要虚拟内存 在第八章我们了解了进程的概念。在计算机系统中&#xff0c;多个进程会共享CPU和内存&#xff0c;当某个进程需要过多的内存空间&#xff0c;那么另外的某个进程可能就会因为无法获得足够的内存空间而无法运行。此外&#xff0c;当某个进程不小心把数据写…
阅读更多...
JAVA毕业设计136—基于Java+Springboot+Vue的房屋租赁管理系统(源代码+数据库)

JAVA毕业设计136—基于Java+Springboot+Vue的房屋租赁管理系统(源代码+数据库)

毕设所有选题&#xff1a; https://blog.csdn.net/2303_76227485/article/details/131104075 基于JavaSpringbootVue的房屋租赁管理系统(源代码数据库)136 一、系统介绍 本项目前后端分离&#xff0c;分为管理员、用户、工作人员、房东四种角色 1、用户/房东&#xff1a; …
阅读更多...
信息收集分类

信息收集分类

在信息收集中&#xff0c;需要收集的信息&#xff1a;目标主机的DNS信息、目标IP地址、子域名、旁站和C段、CMS类型、敏感目录、端口信息、操作系统版本、网站架构、漏洞信息、服务器与中间件信息、邮箱、人员、地址等。 信息收集区别 主动信息收集&#xff1a;直接与目标信息发…
阅读更多...
最新文章

Copyright @ 2022~2023