文档章节

js算法:heap sort 使用堆排序

深山猎人
 深山猎人
发布于 2016/06/27 11:08
字数 441
阅读 153
收藏 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 ]

© 著作权归作者所有

共有 人打赏支持
深山猎人
粉丝 15
博文 40
码字总数 19894
作品 0
朝阳
后端工程师
私信 提问
浅解前端必须掌握的算法(五):堆排序(下)

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

程序猿何大叔
07/05
0
0
六种排序算法的JavaScript实现以及总结

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

DM.Zhong
05/24
0
0
常用排序算法之JavaScript实现

1、插入排序 1)算法简介 插入排序(Insertion-Sort)的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插...

开心303
2014/09/05
0
0
Chrome开发者工具之JavaScript内存分析

内存泄漏是指计算机可用内存的逐渐减少。当程序持续无法释放其使用的临时内存时就会发生。JavaScript的web应用也会经常遇到在原生应用程序中出现的内存相关的问题,如泄漏和溢出,web应用也需...

IanSun
2015/03/14
0
0
Eclipse新建ExtJs4.1的PHP工程之后出现的heap超出的解决方案

今天我用 sencha generate app ext 命令生成了一个extjs4.1的工程 遂而用Eclipse新建了一个PHP工程 用源代码的方式新建 新建完毕 一会儿Eclipse的CPU占用极高 一会儿就弹出窗口错误 提示Jav...

xue777hua
2013/05/21
0
0

没有更多内容

加载失败,请刷新页面

加载更多

分布式锁的实现

redis实现分布式锁 方法1:普通实现方案 实现方式: 使用指令: set key 随机值 ex 5 nx.意思是当key不存在的时候设置key. 如果key存在返回OK,否则返回nil. 实现过程: 1.执行命令set key true ...

grace_233
20分钟前
1
0
解决CKEditor 4 富文本编辑器在图片组件无法显示[上传]选项卡的相关问题

关于解决CKEditor 4 富文本编辑器在图片组件无法显示[上传]选项卡的相关问题。 本文可能会对以下现象得以解决: 图片上传组件,没有 [上传] 选项卡。 资源无法加载 [imgupload] ( Uncaught E...

Eller
24分钟前
0
0
限制php解析、user_agent、php相关配置

11月20日任务 11.28 限定某个目录禁止解析php 11.29 限制user_agent 11.30/11.31 php相关配置 11.28、限定某个目录禁止解析php 核心配置文件内容 <Directory /data/wwwroot/www.123.com/upl...

zgxlinux
28分钟前
1
0
博客园首页新随笔联系订阅管理 随笔

注解Annotation实现原理与自定义注解例子 什么是注解? 对于很多初次接触的开发者来说应该都有这个疑问?Annontation是Java5开始引入的新特征,中文名称叫注解。它提供了一种安全的类似注释的...

onedotdot
46分钟前
4
1
Spring boot + redis 用RedisTemlate实现简单的String key value 操作

springboot集成redis, 简单的key, value缓存操作. 1. application-local.properties # redis on local#spring.redis.port=6379#spring.redis.host=localhost#spring.redis.password=......

园领T
59分钟前
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部