文档章节

js算法:heap sort 使用堆排序

深山猎人
 深山猎人
发布于 2016/06/27 11:08
字数 441
阅读 212
收藏 0

'use strict';

//堆排序

//堆: 完全二叉树
//最大堆定义: 父节点>= 左子节点 父节点 >= 右子节点

//维持最大堆性质
function maxHeapify(arr, i, heapSize) {
  let r = right(i);    //右子节点
  let l = left(i);     //左子节点

  let largest = i;
  //求right,left和parent三者中最大者
  if (r < heapSize && arr[r] > arr[i]) {
    largest = r;
  }

  if (l < heapSize && arr[l] > arr[largest]) {
    largest = l;
  }

  //如果三者最大者不是parent i,那么需要i和相应的最大者进行交换,以便维持最大堆性质
  if (largest != i) {
    //交换
    let max = arr[largest];
    arr[largest] = arr[i];
    arr[i] = max;
    //交换以后,子节点有可能违背了最大堆定义,所以需要递归处理子节点
    maxHeapify(arr, largest, heapSize);
  }
}

//i的右子节点下标
function right(i) {
  return 2 * i + 2;
}

//i的左子节点下标
function left(i) {
  return 2 * i + 1;
}

//构建最大堆
function buildMaxHeap(arr) {
  for(var i=parseInt(arr.length / 2); i >= 0; i--) {
    maxHeapify(arr, i, arr.length);
  }
}

//使用最大堆排序
function maxHeapSort(arr) {
  //因为最大数总是在堆顶,所以每次把堆顶最大数拿出来,然后重新构建最大堆,再把堆顶数拿出来,以此递归,就能拿到一个从小到大排列的数组
  buildMaxHeap(arr);
  let heapSize = arr.length;
  for(var i=arr.length-1; i>0; i--) {
    let max = arr[0];
    arr[0] = arr[i];
    arr[i] = max;
    heapSize = heapSize - 1;
    maxHeapify(arr, 0, heapSize);
  }
}


//随机获取一个数组
function randNum() {
  return parseInt(Math.random() * 100);
}

function getRandArr(length) {
  var arr = [];
  for(var i=0; i<length; i++) {
    arr.push(randNum());
  }
  return arr;
}

var arr = getRandArr(10);
console.info("随机生成的数组:", arr);
maxHeapSort(arr);
console.info("用堆排序后数组:", arr);

//某次运行结果如下:
//随机生成的数组: [ 29, 92, 50, 89, 96, 64, 36, 47, 34, 96 ]
//用堆排序后数组: [ 29, 34, 36, 47, 50, 64, 89, 92, 96, 96 ]

© 著作权归作者所有

深山猎人
粉丝 17
博文 41
码字总数 20647
作品 0
朝阳
后端工程师
私信 提问
加载中

评论(0)

浅解前端必须掌握的算法(五):堆排序(下)

前言 虽然前端面试中很少会考到算法类的题目,但是你去比如像腾讯一样的大厂面试的时候就知道了,对基本算法的掌握对于从事计算机科学技术的我们来说,还是必不可少的,每天花上 10 分钟,轻...

程序猿何大叔
2018/07/05
0
0
十大经典排序算法(Javascript实现)

前言 总括: 本文结合动图详细讲述了十大经典排序算法用Javascript实现的过程。 原文博客地址:十大经典排序算法 公众号:「菜鸟学前端」,回复「666」,获取一揽子前端技术书籍 人生有情泪沾...

Damonare
02/07
0
0
JavaScript 数据结构与算法之美 - 归并排序、快速排序、希尔排序、堆排序

1. 前言 算法为王。 想学好前端,先练好内功,只有内功深厚者,前端之路才会走得更远。 笔者写的 JavaScript 数据结构与算法之美 系列用的语言是 JavaScript ,旨在入门数据结构与算法和方便...

天明夜尽
2019/07/24
0
0
六种排序算法的JavaScript实现以及总结

最近几天在系统的复习排序算法,之前都没有系统性的学习过,也没有留下过什么笔记,所以很快就忘了,这次好好地学习一下。 首先说明为了减少限制,以下代码通通运行于Node V8引擎而非浏览器,...

DM.Zhong
2018/05/24
0
0
前端进阶(第一期)-调用堆栈笔记

1-1 理解 Javascript 执行上下文和执行栈 原文地址 知识点有: JavaScript程序的内部执行机制; 理解执行上下文和执行栈; 理解以上知识点有助于理解JavaScript的提升机制、作用域和闭包 执行...

xszi
2018/12/04
0
0

没有更多内容

加载失败,请刷新页面

加载更多

JVM解毒——JVM与Java体系结构

你是否也遇到过这些问题? 运行线上系统突然卡死,系统无法访问,甚至直接OOM 想解决线上JVM GC问题,但却无从下手 新项目上线,对各种JVM参数设置一脸懵逼,直接默认,然后就JJ了 每次面试都...

大猿帅
54分钟前
70
0
数据结构与算法系列二(复杂度分析)

1.引子 1.1.为什么要学习数据结构与算法? 有人说,数据结构与算法,计算机网络,与操作系统都一样,脱离日常开发,除了面试这辈子可能都用不到呀! 有人说,我是做业务开发的,只要熟练API...

yhhitall
55分钟前
50
0
开发的Web应用界面太难看?Kendo UI R1 2020工具全新发布帮你忙

Kendo UI for jQuery R1 2020试用版下载 2020年,Kendo UI全新出发,发布R1 2020!此版本在Kendo UI bundle包中的所有库中进行了一些更新,包括jQuery,Angular,React和Vue UI库!本系列文章...

FILA6666
今天
84
0
Spring是什么?Spring 的优点?

Spring是什么? Spring是一个轻量级的IoC和AOP容器框架。是为Java应用程序提供基础性服务的一套框架,目的是用于简化企业应用程序的开发,它使得开发者只需要关心业务需求。常见的配置方式有三...

无名氏的程序员
今天
68
0
cocoapods

1.卡住 Cloning spec repo `cocoapods` from `git@github.com:CocoaPods/Specs.git` 解决办法: pod setupcd ~/.cocoapods/repos git clone --depth 1 https://github.com/CocoaPods/Sp......

walking_yxf
今天
60
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部