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

一些概念

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

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

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

最大堆

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

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

解释：

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

实现

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 = parent
			parent = 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])) break
			this.#swap(k, j)
			k = j
		}
	}
}

测试

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 ]

最小堆

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

实现

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 = parent
			parent = 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])) break
			this.#swap(k, j)
			k = j
		}
	}
}

测试

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]

堆（自定义比较函数）

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

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 = parent
			parent = 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])) break
			this.#swap(k, j)
			k = j
		}
	}
}

测试

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 ，跟上面处理边界不一样。

实现

function heapSort (arr) {
	// arr = arr.slice(0) // 是否原地排序
	let N = arr.length - 1
	if (!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)) break
			exch(k, j)
			k = j
		}
	}
	// 构建堆
	for(let i = Math.floor(N/2); i >= 0; i--) {
		sink(i)
	}
	// 堆有序
	while (N > 0) {
		exch(0, N--)
		sink(0)
	}
}

另一个实现

function heapSort (arr) {
	// arr = arr.slice(0) // 是否原地排序
	let N = arr.length
	if (!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])) break
			swap(k, j)
			k = j
		}
	}
	// 构建堆
	for(let i = Math.floor(N/2); i >= 0; i--) {
		sink(i)
	}
	// 堆有序
	while (N > 1) {
		swap(0, --N)
		sink(0)
	}
}

测试

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

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/552927.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

类和对象-封装-设计案例1-立方体类

类和对象-封装-设计案例1-立方体类

#include<bits/stdc.h> using namespace std; class Cube{public://设置长void setL(int l){m_Ll;} //获取长int getL(){return m_L;}//设置宽 void setW(int w){m_Ww;}//获取宽 int getW(){return m_W;}//设置高 void setH(int h){m_Hh;}//获取高int getH(){return m_H;…
阅读更多...
【机器学习300问】72、神经网络的隐藏层数量和各层神经元节点数如何影响模型的表现？

【机器学习300问】72、神经网络的隐藏层数量和各层神经元节点数如何影响模型的表现？

评估深度学习的模型的性能依旧可以用偏差和方差来衡量。它们反映了模型在预测过程中与理想情况的偏离程度&#xff0c;以及模型对数据扰动的敏感性。我们简单回顾一下什么是模型的偏差和方差&#xff1f; 一、深度学习模型的偏差和方差 偏差&#xff1a;衡量模型预测结果的期望…
阅读更多...
JAVAEE—UDP协议TCP协议/三次握手四次挥手

JAVAEE—UDP协议TCP协议/三次握手四次挥手

文章目录 UDP协议UDP协议的段格式UDP的传输过程校验和无连接 TCP协议TCP报文的格式段有连接可靠性确认应答超时重传如果ACK丢了呢&#xff1f; 序号和确认序号 连接的构建和断开连接的构建&#xff08;三次握手&#xff09;三次握手的作用为什么握手是三次&#xff0c;而不是四…
阅读更多...
微信小程序的常用API ①

微信小程序的常用API ①

前言&#xff1a;什么是微信小程序的API&#xff1f; &#xff08;1&#xff09;微信小程序的API是由宿主环境提供的。通俗来说API是一种接口函数&#xff0c;把函数封装起来给开发者使用&#xff0c;这样好多功能都无需开发者去实现&#xff0c;直接调用即可。 &#xff08;…
阅读更多...
工业电脑在ESOP工作站行业应用

工业电脑在ESOP工作站行业应用

ESOP工作站行业应用 项目背景 E-SOP是实现作业指导书电子化&#xff0c;并统一管理和集中控制的一套管理信息平台。信迈科技的ESOP终端是一款体积小巧功能齐全的高性价比工业电脑&#xff0c;上层通过网络与MES系统连接&#xff0c;下层连接显示器展示作业指导书。ESOP控制终…
阅读更多...
Covalent Network（CQT）宣布推出面向 Cronos 生态的捐赠计划与 API 积分，为 Web3 创新赋能

Covalent Network（CQT）宣布推出面向 Cronos 生态的捐赠计划与 API 积分，为 Web3 创新赋能

为了促进 Web3 领域的创新&#xff0c;Covalent Network&#xff08;CQT&#xff09;宣布将其捐赠计划向 Cronos 生态系统中的开发者拓展。这一战略性举措&#xff0c;旨在通过向 Cronos 网络中基于 Covalent Network&#xff08;CQT&#xff09;API 构建的项目提供支持和资源&…
阅读更多...
OpenHarmony实战开发-如何使用Navigation实现多设备适配。

OpenHarmony实战开发-如何使用Navigation实现多设备适配。

介绍 在应用开发时&#xff0c;一个应用需要适配多终端的设备&#xff0c;使用Navigation的mode属性来实现一套代码&#xff0c;多终端适配。 效果图预览 使用说明 将程序运行在折叠屏手机或者平板上观看适配效果。 实现思路 本例涉及的关键特性和实现方案如下&#xff1a…
阅读更多...
高版本Android studio 使用Markdown无法预览（已解决）

高版本Android studio 使用Markdown无法预览（已解决）

目录 概述 解决方法 概述 本人升级Android studio 当前版本为Android Studio Jellyfish | 2023.3.1 RC 2导致Markdown无法预览。 我尝试了很多网上的方法都无法Markdown解决预览问题&#xff0c;包括升级插件、安装各种和Markdown相关的插件及使用“Choose Boot Java Runtim…
阅读更多...
Linux 操作系统编译器、静态库、动态库

Linux 操作系统编译器、静态库、动态库

1、编辑器 1.1、vim的安装 指令&#xff1a;sudo apt-get install vim 1.2 vim的使用 格式&#xff1a;vim 文件名 如果文件存在&#xff0c;只打开&#xff0c;文件不存在&#xff0c;创建并打开 vim的4中模式&#xff1a; 命令模式&#xff0c;插入模式&#xff0c;地行模…
阅读更多...
springboot Logback 不同环境，配置不同的日志输出路径

springboot Logback 不同环境，配置不同的日志输出路径

1.背景&#xff1a; mac 笔记本开发&#xff0c;日志文件写到/data/logs/下&#xff0c;控制台报出&#xff1a;Failed to create parent directories for [/data/logs/........... 再去手动在命令窗口创建文件夹data&#xff0c;报Read-only file system 2.修改logback-spri…
阅读更多...
Hbase的shell命令（详细）

Hbase的shell命令（详细）

一、help 1.help 显示命名的分组情况 2.help 命令名称 查看命令的具体使用&#xff0c;包括命令的作用和用法。 举例&#xff1a;help list 二、general 组&#xff08;普通命令组&#xff09; 命令 描述 …
阅读更多...
Redux极客园项目初始化搭建

Redux极客园项目初始化搭建

基本结构搭建 实现步骤 在 Login/index.js 中创建登录页面基本结构在 Login 目录中创建 index.scss 文件&#xff0c;指定组件样式将 logo.png 和 login.png 拷贝到 assets 目录中 代码实现 pages/Login/index.js import ./index.scss import { Card, Form, Input, Button }…
阅读更多...
【第十二届“泰迪杯”数据挖掘挑战赛】【2024泰迪杯】B题基于多模态特征融合的图像文本检索—更新（正式比赛）

【第十二届“泰迪杯”数据挖掘挑战赛】【2024泰迪杯】B题基于多模态特征融合的图像文本检索—更新（正式比赛）

【第十二届“泰迪杯”数据挖掘挑战赛】【2024泰迪杯】B题基于多模态特征融合的图像文本检索—更新&#xff08;正式比赛&#xff09; 往期链接&#xff1a; 【第十二届“泰迪杯”数据挖掘挑战赛】【2024泰迪杯】B题基于多模态特征融合的图像文本检索—解题全流程&#xff08;…
阅读更多...
安防视频监控/视频集中存储EasyCVR平台级联时，下级平台未发流是什么原因？

安防视频监控/视频集中存储EasyCVR平台级联时，下级平台未发流是什么原因？

安防视频监控/视频集中存储/云存储/磁盘阵列EasyCVR平台可拓展性强、视频能力灵活、部署轻快&#xff0c;可支持的主流标准协议有国标GB28181、RTSP/Onvif、RTMP等&#xff0c;以及支持厂家私有协议与SDK接入&#xff0c;包括海康Ehome、海大宇等设备的SDK等。平台既具备传统安…
阅读更多...
PPTist在线编辑、播放幻灯片

PPTist在线编辑、播放幻灯片

PPTist简介 “一个基于 Vue3.x TypeScript 的在线演示文稿&#xff08;幻灯片&#xff09;应用&#xff0c;还原了大部分 Office PowerPoint 常用功能&#xff0c;支持 文字、图片、形状、线条、图表、表格、视频、音频、公式 几种最常用的元素类型&#xff0c;每一种元素都拥…
阅读更多...
免费申请泛域名证书

免费申请泛域名证书

通配符证书是一种比较特殊的SSL/TLS 证书&#xff0c;可用于保护多个域名&#xff08;含主域名&#xff09;&#xff0c;由域名字段中的通配符 (*) 指示。这种证书主要用于具有很多子域的组织。通配符证书对主域及其所有次级子域有效。 对于免费通配符证书而言&#xff0c;目前…
阅读更多...
【C++杂货铺】继承

【C++杂货铺】继承

目录 &#x1f308;前言&#x1f308; &#x1f4c1; 继承的概念和定义 &#x1f4c2; 概念 &#x1f4c2; 定义 &#x1f4c1; 基类和派生类对象赋值转换 &#x1f4c1; 继承中的作用域 &#x1f4c1; 派生类的默认成员函数 构造函数 析构函数 拷贝构造函数 赋值重载…
阅读更多...
ppt技巧：​如何将两个PPT幻灯片文件合并成一个？

ppt技巧：​如何将两个PPT幻灯片文件合并成一个？

第一种方式&#xff1a;复制粘贴幻灯片 1. 打开第一个PPT幻灯片文件&#xff0c;确保你已经熟悉该文件的内容和布局。 2. 打开第二个PPT幻灯片文件&#xff0c;浏览其中的所有幻灯片&#xff0c;选择你想要合并到第一个文件中的幻灯片。 3. 使用快捷键CtrlC&#xff08;Wind…
阅读更多...
【C++类和对象】拷贝构造与赋值运算符重载

【C++类和对象】拷贝构造与赋值运算符重载

&#x1f49e;&#x1f49e; 前言 hello hello~ &#xff0c;这里是大耳朵土土垚~&#x1f496;&#x1f496; &#xff0c;欢迎大家点赞&#x1f973;&#x1f973;关注&#x1f4a5;&#x1f4a5;收藏&#x1f339;&#x1f339;&#x1f339; &#x1f4a5;个人主页&#x…
阅读更多...
GAN反演+老照片修复

GAN反演+老照片修复

关于老照片修复~~~~~上图为运行腾讯ARC的模型之后的效果图 其使用的模型&#xff0c;GFP-GAN&#xff0c;Towards Real-World Blind Face Restoration with Generative Facial Prior&#xff0c;理解记录如下&#xff1a; Abstract: In this work, we propose GFP-GAN that …
阅读更多...
最新文章

Copyright @ 2022~2023