堆排序的JavaScript实现
2024-08-31 10:13:43
思想
把数组当做二叉树来排序:
- 索引0是树的根节点;
- 除根节点外,索引为N的节点的父节点索引是(N-1)/2;
- 索引为N的节点的左子节点索引是 2*N+1;
- 索引为N的节点的右子节点索引是 2*N+2;
关于二叉树相关tips:
- 满二叉树:深度为k且有2^k-1个节点的二叉树
- 完全二叉树:有n个节点的二叉树,当且仅当其每个节点按从上到下、从左至右的顺序进行编号,其编号与满二叉树中1至n的节点编号一一对应
- 第k层的最大节点数: 2^(k-1)
- 有n个节点的完全二叉树中最后一个有子节点的节点的序号:Math.floor(n/2-1)
代码
function heapSort(arr) {
let heapSize = arr.length;
buildHeap(arr);//构造一个所有节点都满足arr[parent[i]] > arr[i]的堆结构数组,这样就把值最大的那个节点换到了根节点
while(heapSize > 1) { //*1
//在当前树中,交换位于根节点的最大值和最后一个节点的值,这样就把最大值排在了最后一个节点,这样就排好了最大值
const temp = arr[0];
arr[0]=arr[heapSize-1];
arr[heapSize-1] = temp;
heapSize--;//当前树中最后一个节点已经排好了值,故后面就不用再考虑这个节点,故新的树的大小减一
if (heapSize>1) {
heapify(arr, heapSize, 0);//上面的交换操作产生了新的根节点,新的根节点只是通过跟最后一个节点交换得到的值,故新的根节点不满足条件arr[parent[i]]<arr[i],所以要对根节点再次进行h
}
}
}
/**
* @description 构造一个所有节点都满足arr[parent[i]] > arr[i]的堆结构数组
* @param {Array} arr 待排序数组
*/
function buildHeap(arr) {
const heapSize = arr.length;
const firstHeapifyIndex = Math.floor(heapSize/2-1);//从树的倒数第二层的最后一个有子节点的节点(对于满二叉树就是倒数第二层的最后一个节点)开始进行heapify处理。Math.floor(heapSize/2-1)就是这个最后一个有子节点的节点索引。
for (let i=firstHeapifyIndex; i >= 0; i--) {//从0到firstHeapifyIndex都要进行heapify处理,才能把最大的那个节点换到根节点
heapify(arr, heapSize, i);
}
}
/**
* @description 以数组arr的前heapSize个节点为树,对其中索引为i的节点向子节点进行替换,直到满足从i往下的子节点都有arr[parent[i]]>=arr[i]
* @param {*} arr TYPE Array 待排序的数组
* @param {*} heapSize TYPE Number 待排序的数组中要作为当前树处理的从前往后数的节点个数,即待排序数组中前heapSize个点是要作为树来处理
* @param {*} i TYPE Number arr数组中、heapSize长度的树中的当前要进行往子节点替换的节点的索引
*/
function heapify(arr, heapSize, i) {
const leftIndex = i * 2 + 1;//索引i的节点的左子节点索引
const rightIndex = i * 2 + 2;//索引i的节点的右子节点索引
let biggestValueIndex = i;
if (leftIndex < heapSize && arr[leftIndex] > arr[biggestValueIndex]) {
//节点的最大index为heapSize-1
//注意:这两次比较要跟arr[biggestValueIndex]比较,不能跟arr[i]比较,因为biggestValueIndex是会在左右i之间更新的
biggestValueIndex = leftIndex; //如果左子节点的值大于biggestValueIndex的值(此时就是根节点的值),那么更新biggestValueIndex为左子节点索引
}
if (rightIndex < heapSize && arr[rightIndex] > arr[biggestValueIndex]) {
biggestValueIndex = rightIndex;//如果右子节点的值大于biggestValueIndex的值(此时可能是根节点的值,也可能是左子节点的值),那么更新biggestValueIndex为右子节点索引
}
if (biggestValueIndex !== i) { //如果biggestValueIndex是左子节点索引或右子节点索引,那么交换根节点与biggestValueIndex节点的值
const temp = arr[i];
arr[i] = arr[biggestValueIndex];
arr[biggestValueIndex] = temp;
//交换后,被交换的那个子节点(左子节点或右子节点)往下可能就不再满足[parent[i]]>=arr[i],所以要继续对biggestValueIndex进行heaify处理,即将biggestValueIndex可能需要和子节点进行值交换,直到树的这个分支到叶子节点都满足arr[parent[i]]>=arr[i]
heapify(arr, heapSize, biggestValueIndex);//要
}
}
工作过程
待画图
性能分析
- 时间复杂度:最好、平均、最坏都是 O(nlogn)
- 空间复杂度: O(1),不稳定
延伸:如果数组数量大于10,只找出最大的10个值呢?
上述代码的*1行换成:
while(heapSize > arr.length - 10)
参考资料
-《学习JavaScript数据结构和算法》10.1.6
-《数据结构(C语言版)》9.4.2
最新文章
- 关于SQL Server 安装程序在运行 Windows Installer 文件时遇到错误
- nginx.conf详解
- mima开发实列
- ASP.NET Global Application_Error事件中访问Session报错 解决
- OS实验一实验报告
- 黄聪:让WordPress主题支持语言本地化(使用poedit软件实现中文翻译功能)
- poj 2567 Code the Tree 河南第七届省赛
- ua实现类似 www.taobao.com 在手机上打开自动转变为 m.taobao.com 的域名转换
- php转义和去掉html、php标签函数
- .net链接Oracle数据操作类库
- javascript第二遍基础学习笔记(一)
- Apache Commons 工具类介绍及简单使用
- python基础学习05(核心编程第二版)部分
- Android 异步查询框架AsyncQueryHandler的使用
- win10下maven的安装与配置
- 怎么解决mysql 执行SQL过长问题------------?
- Windows右键菜单设置与应用技巧
- Java中的继承:父类和子类的关系
- Day16 Django深入讲解
- EXC_BAD_ACCESS(code...)坏内存访问 调试
热门文章
- picasso设置背景图片
- html post
- [原创]java WEB学习笔记29:Cookie Demo 之自动登录
- 【leetcode刷题笔记】Max Points on a Line
- 20145239 GDB调试汇编堆栈过程分析
- day4 内置函数 迭代器&;生成器 yield总结 三元运算 闭包
- 国内ADSL用户的带宽一般都是1M、2M、3M的,理论上的下载速度分别是128K/S、256K/S、384K/S。
- 【转】Struts2的线程安全 和Struts2中的设计模式----ThreadLocal模式
- JS高阶函数的理解(函数作为参数传递)
- Mac 上Sublime Text 2配置lua环境