详解堆的javascript实现方法

堆的定义

最大(最小)堆是一棵每一个节点的键值都不小于(大于)其孩子(如果存在)的键值的树。大顶堆是一棵完全二叉树,同时也是一棵最大树。小顶堆是一棵完全完全二叉树,同时也是一棵最小树。

另外,记住这两个概念,对写代码太重要了:

1、父节点和子节点的关系:看定义

2、完全二叉树:参考[2]

基本操作

1、Build(构建堆)

2、Insert(插入)

3、Delete(删除:最小或者最大的那个)

代码实现

首先,写代码前有两个非常重要的点:

1、用一个数组就可以作为堆的存储结构,非常简单而且易操作;

2、另外同样因为是数组作为存储结构,所以父子节点之间的关系就能根据索引就轻松找到对方了。

对于JavaScript以0作为数组索引开始,关系如下:

nLeftIndex = 2 * (nFatherIndex+1) - 1;
nRightIndex = 2* (nFatherIndex+1);

前面提到注意两个概念,是有助于理解的:

1、因为是数组,所以父子节点的关系就不需要特殊的结构去维护了,索引之间通过计算就可以得到,省掉了很多麻烦。如果是链表结构,就会复杂很多;

2、完全二叉树的概念可以参考[2],要求叶子节点从左往右填满,才能开始填充下一层,这就保证了不需要对数组整体进行大片的移动。这也是随机存储结构(数组)的短板:删除一个元素之后,整体往前移是比较费时的。这个特性也导致堆在删除元素的时候,要把最后一个叶子节点补充到树根节点的缘由

代码实现:

/******************************************************
* file : 堆
* author : "page"
* time : "2016/11/02"
*******************************************************/
function Heap()
{
 this.data = [];
}

Heap.prototype.print = function () {
 console.log("Heap: " + this.data);
}

Heap.prototype.build = function(data){
 // 初始化
 this.data = [];
 if (!data instanceof Array)
 return false;

 // 入堆
 for (var i = 0; i < data.length; ++i) {
 this.insert(data[i]);
 }

 return true;
}

Heap.prototype.insert = function( nValue ){
 if (!this.data instanceof Array) {
 this.data = [];
 }

 this.data.push(nValue);
 // 更新新节点
 var nIndex = this.data.length-1;
 var nFatherIndex = Math.floor((nIndex-1)/2);
 while (nFatherIndex > 0){
 if (this.data[nIndex] < this.data[nFatherIndex]) {
 var temp = this.data[nIndex];
 this.data[nIndex] = this.data[nFatherIndex];
 this.data[nFatherIndex] = temp;
 }

 nIndex = nFatherIndex;
 nFatherIndex = Math.floor((nIndex-1)/2);
 }
}

Heap.prototype.delete = function( ){
 if (!this.data instanceof Array) {
 return null;
 }

 var nIndex = 0;
 var nValue = this.data[nIndex];
 var nMaxIndex = this.data.length-1;
 // 更新新节点
 var nLeaf = this.data.pop();
 this.data[nIndex] = nLeaf;

 while (nIndex < nMaxIndex ){
 var nLeftIndex = 2 * (nIndex+1) - 1;
 var nRightIndex = 2 * (nIndex+1);

 // 找最小的一个子节点(nLeftIndex < nRightIndex)
 var nSelectIndex = nLeftIndex;
 if (nRightIndex < nMaxIndex) {
 nSelectIndex = (this.data[nLeftIndex] > this.data[nRightIndex]) ? nRightIndex : nLeftIndex;
 }

 if (nSelectIndex < nMaxIndex && this.data[nIndex] > this.data[nSelectIndex] ){
 var temp = this.data[nIndex];
 this.data[nIndex] = this.data[nSelectIndex];
 this.data[nSelectIndex] = temp;
 }

 nIndex = nSelectIndex;
 }

 return nValue;
}
// test
var heap = new Heap();
heap.build([1, 3, 5, 11, 4, 6, 7, 12, 15, 10, 9, 8]);
heap.print();
// insert
heap.insert(2);
heap.print();
// delete
heap.delete();
heap.print();

关于JavaScript的几点小结

这里是采用面向对象的一种实现方法,感觉上不是太优雅,不知道还有没有更好的表示方法和写法;

学习了数组的几个用法:push和pop的操作太好用了;

判断数组的方式也是临时从网上搜的(instanceof),印象不深刻,不用的话下次估计还是有可能忘掉。

参考

[1]《数据结构和算法分析:C语言描述》

[2]图解数据结构(8)——二叉堆

[3]>数据结构:堆

总结

JavaScript的数组实现了push和pop这些操作,许多其他语言也提供了类似的数据结构和操作(比如C++的Vector),同时也支持随机操作。所以,我开始想如果这些结构上简单的加上自动排序的概念,那么一个堆就轻松搞定了,后面看到C++ STL的make_heap就知道自己知道的太少了,但也庆幸自己思维方式是对的。JavaScript的没有去查,我想有或者实现起来很容易;
自己去实现了之后,发现这个结构也很简单,只要你肯去跟它亲密接触一次就可以了;

JavaScript的细节部分还是不太了解,比如数组的应用上还要再翻资料才能用;对于JavaScript的灵魂还是没有接触到,精髓部分需要不断的学习和练习;

这些代码,只要你去了解了概念,了解了编程的基础,就可以写的出来。但是,代码还可以写的更简洁,比如delete函数求最小的子节点的时候,左右节点的索引就不需要比较,肯定是左边的小。代码部分感觉还是可以继续优化和精简的。

以上就是这篇文章的全部内容了,希望本文的内容对大家的学习或者工作能带来一定的帮助,如果有疑问大家可以留言交流,谢谢大家对我们的支持。

(0)

相关推荐

  • JavaScript调用堆栈及setTimeout使用方法深入剖析

    Javascript中会经常用到setTimeout来推迟一个函数的执行,如: 复制代码 代码如下: setTimeout(function(){alert("Hello World");},1000); 会在执行到这句话后延迟1秒钟来弹出alert窗口.那么再看这一段: 复制代码 代码如下: function a(){ setTimeout(function() {alert(1)}, 0); alert(2); } a(); 注意这段代码中的setTimeout延迟设为了0,就是延

  • JavaScript把数组作为堆栈使用的方法

    本文实例讲述了JavaScript把数组作为堆栈使用的方法.分享给大家供大家参考.具体如下: JavaScript把数组作为堆栈使用的代码范例,支持堆栈常用的push和pop方法 <script type="text/javascript"> var numbers = ["one", "two", "three", "four"]; numbers.push("five")

  • Javascript堆排序算法详解

    堆排序分为两个过程: 1.建堆. 堆实质上是完全二叉树,必须满足:树中任一非叶子结点的关键字均不大于(或不小于)其左右孩子(若存在)结点的关键字. 堆分为:大根堆和小根堆,升序排序采用大根堆,降序排序采用小根堆. 如果是大根堆,则通过调整函数将值最大的节点调整至堆根. 2.将堆根保存于尾部,并对剩余序列调用调整函数,调整完成后,再将最大跟保存于尾部-1(-1,-2,...,-i),再对剩余序列进行调整,反复进行该过程,直至排序完成. 复制代码 代码如下: //调整函数 function head

  • JS实现队列与堆栈的方法

    本文实例讲述了JS实现队列与堆栈的方法.分享给大家供大家参考,具体如下: 在面向对象的程序设计里,一般都提供了实现队列(queue)和堆栈(stack)的方法,而对于JS来说,我们可以实现数组的相关操作,来实现队列和堆栈的功能,看下面的相关介绍. 一.看一下它们的性质,这种性质决定了它们的使用场合 队列:是一种支持先进先出(FIFO)的集合,即先被插入的数据,先被取出! 堆栈:是一种支持后进先出(LIFO)的集合,即后被插入的数据,先被取出! 二.看一下实现的代码(JS代码) var a=new

  • java自带的工具Jstack截取进程中的堆栈信息

    在Java软件的使用过程中,有时会莫名的出现奇怪的问题.而这些问题常常无法使用日志信息定位,这时我们就需要通过查看进程内部线程的堆栈调用关系来分析问题出在哪里. 举个例子,当我们在做某个操作时,莫名的会弹出多个警告框,其中有些信息是正常的,有些则不是.对于这些错误的警告信息,我们该如何定位是哪个位置的代码出现了错误弹出的框呢? 我们就需要在弹框以后,去查看软件的各个线程,去查找究竟是哪个线程导致了该问题.可是有时因为环境.时间等问题,我们根本不能拿着IDE去调试, 只能通过工具软件拍下内存快照,

  • JavaScript实现显示函数调用堆栈的方法

    本文实例讲述了JavaScript实现显示函数调用堆栈的方法.分享给大家供大家参考,具体如下: 许多大型的JavaScript应用程序间的函数调用关系是非常复杂的,在开发或者调试过程中,经常需要跟踪某个函数是由哪些函数调用后才触发执行的,弄清楚这些函数的调用顺序对我们理解代码的数据流向是非常重要的. Firebug提供了console.trace()来显示函数堆栈,在需要调试的地方加上下面的一行代码就能显示该函数调用时的上下文关系.IE6就没有这么方便了,它没有提供显示函数堆栈的工具,当不可避免

  • js自动生成的元素与页面原有元素发生堆叠的解决方法

     商品属性和商品规格是js动态生成的元素,商品扩展信息的两个文本框是原有的元素,他们发生堆叠,我以为是我生成的元素所在div大小不固定导致的,因为商品规格的下面复选框是第二次ajax生成的,我怀疑第二次ajax是不是不能将页面原有元素向下推到合适的位置. 搞了几个小时,尝试固定元素所在容器div的的大小,但是不好固定啊,元素的个数是不定的,尝试改变属性和规格的生成顺序,属性部分堆到规格部分上去了,规格部分的元素怎么不独立占位置呢,后来才想到会不会是浮动了,去除浮动,给原有元素(商品扩展信息部分)

  • 使用堆实现Top K算法(JS实现)

    先来聊一聊Top K算法,具体内容如下 应用场景: 搜索引擎会通过日志文件把用户每次检索使用的所有检索串都记录下来,每个查询串的长度为1-255字节.         假设目前有一千万个记录(这些查询串的重复度比较高,虽然总数是1千万,但如果除去重复后,不超过3百万个.一个查询串的重复度越高,说明查询它的用户越多,也就是越热门.),请你统计最热门的10个查询串,要求使用的内存不能超过1G. 必备知识: 什么是哈希表?         哈希表(Hash table,也叫散列表),是根据关键码值(K

  • JavaScript数组实现数据结构中的队列与堆栈

    一.队列和堆栈的简单介绍 1.1.队列的基本概念 队列:是一种支持先进先出(FIFO)的集合,即先被插入的数据,先被取出! 如下图所示: 1.2.堆栈的基本概念 堆栈:是一种支持后进先出(LIFO)的集合,即后被插入的数据,先被取出! 如下图所示: 二. 在JavaScript中实现队列和堆栈 在JavaScript中实现队列和数组主要是通过数组,js数组中提供了以下几个方法可以让我们很方便实现队列和堆栈: •shift:从数组中把第一个元素删除,并返回这个元素的值. •unshift: 在数组

  • 详解堆的javascript实现方法

    堆的定义 最大(最小)堆是一棵每一个节点的键值都不小于(大于)其孩子(如果存在)的键值的树.大顶堆是一棵完全二叉树,同时也是一棵最大树.小顶堆是一棵完全完全二叉树,同时也是一棵最小树. 另外,记住这两个概念,对写代码太重要了: 1.父节点和子节点的关系:看定义 2.完全二叉树:参考[2] 基本操作 1.Build(构建堆) 2.Insert(插入) 3.Delete(删除:最小或者最大的那个) 代码实现 首先,写代码前有两个非常重要的点: 1.用一个数组就可以作为堆的存储结构,非常简单而且易操作

  • 详解如何在Javascript中使用Object.freeze()

    Object.freeze() Object.freeze() 方法可以冻结一个对象.一个被冻结的对象再也不能被修改:冻结了一个对象则不能向这个对象添加新的属性,不能删除已有属性,不能修改该对象已有属性的可枚举性.可配置性.可写性,以及不能修改已有属性的值.此外,冻结一个对象后该对象的原型也不能被修改.freeze() 返回和传入的参数相同的对象 用法 const objectExample = { prop1: 20, prop2: "羊先生" }; // 默认情况下,我们可以根据需

  • 详解Java String中intern方法的原理与使用

    目录 简介 常量池简介 intern方法简介(JDK7) 原理(JDK6与JDK7) 例程测试 例程分析 jdk1.6 jdk1.7 应用实例 简介 本文介绍Java的String的intern方法的原理. 常量池简介 在 JAVA 语言中有8种基本类型和一种比较特殊的类型String.这些类型为了使他们在运行过程中速度更快,更节省内存,都提供了一种常量池(在方法区)的概念.常量池就类似一个JAVA系统级别提供的缓存.8种基本类型的常量池都是系统协调的,String类型的常量池比较特殊. Str

  • 详解如何用JavaScript编写一个单元测试

    目录 为什么要进行单元测试? 范围界定和编写单元测试 保持单元测试简短而简单 考虑正面和负面的测试用例 分解长而复杂的函数 避免网络和数据库连接 如何编写单元测试 创建一个新项目 实现一个类 配置和添加我们的第一个单元测试 添加更多单元测试 修复错误 最后 测试代码是确保代码稳定的第一步.能做到这一点的最佳方法之一就是使用单元测试,确保应用程序中的每个较小的功能都按应有的方式运行——尤其是当应用程序接收到极端或无效输入,甚至可能有害的输入时. 为什么要进行单元测试? 进行单元测试有许多不同的方法

  • 详解Java 本地接口 JNI 使用方法

    详解Java 本地接口 JNI 使用方法 对于Java程序员来说,Java语言的好处和优点,我想不用我说了,大家自然会说出很多一套套的.但虽然我们作为java程序员,但我们不得不承认java语言也有一些它本身的缺点.比如在性能.和底层打交道方面都有它的缺点.所以java就提供了一些本地接口,他主要的作用就是提供一个标准的方式让java程序通过虚拟机与原生代码进行交互,这也就是我们平常常说的java本地接口(JNI--java native Interface).它使得在 Java 虚拟机 (VM

  • 详解jQuery中ajax.load()方法

    jQuery load() 方法 jQuery load() 方法是简单但强大的 AJAX 方法. load() 方法从服务器加载数据,并把返回的数据放入被选元素中. 语法: $(selector).load(URL,data,callback); load()函数用于从服务器加载数据,并使用返回的html内容替换当前匹配元素的内容. load()函数默认使用GET方式,如果提供了对象形式的数据,则自动转为POST方式. 因为默认使用的是Get请求方式,所以我们也可以在url加数据进行提交. 例

  • 详解vue beforeEach 死循环问题解决方法

    什么是beforeEach? beforeEach 是一个vue-router的路由导航钩子,一般我用它做路由守卫. 什么是路由守卫? 路由跳转前做一些验证,比如登录验证,是网站中的普遍需求.对此,vue-route 提供的beforeRouteUpdate可以方便地实现导航守卫(navigation-guards).导航守卫(navigation-guards)这个名字,听起来怪怪的,但既然官方文档是这样翻译的,就姑且这么叫吧.** 文档地址:https://router.vuejs.org/

  • 详解ES6新增字符串扩张方法includes()、startsWith()、endsWith()

    当有人问到用来确定一个字符串是否包含在另一个字符串中有哪些方法时,我们会不假思索回答道:indexOf方法.其实,ES6 又提供了三种新方法includes().startsWith().endsWith(),也是比较好用的. indexOf方法在这里就不多说了,大家都比较熟悉,意思就是:返回给定元素在数组中第一次出现的位置,返回结果是匹配开始的位置,如果没有出现则返回-1. 下面详细介绍ES6新增的这三种方法: ①includes():返回布尔值,表示是否找到了参数字符串. 如下所示: let

  • Python pandas 列转行操作详解(类似hive中explode方法)

    最近在工作上用到Python的pandas库来处理excel文件,遇到列转行的问题.找了一番资料后成功了,记录一下. 1. 如果需要爆炸的只有一列: df=pd.DataFrame({'A':[1,2],'B':[[1,2],[1,2]]}) df Out[1]: A B 0 1 [1, 2] 1 2 [1, 2] 如果要爆炸B这一列,可以直接用explode方法(前提是你的pandas的版本要高于或等于0.25) df.explode('B') A B 0 1 1 1 1 2 2 2 1 3

  • 详解Android aidl的使用方法

    AIDL是Android中IPC(Inter-Process Communication)方式中的一种,AIDL是Android Interface definition language的缩写(对于小白来说,AIDL的作用是让你可以在自己的APP里绑定一个其他APP的service,这样你的APP可以和其他APP交互.) AIDL只是Android中众多进程间通讯方式中的一种方式, AIDL和Messenger的区别: Messenger不适用大量并发的请求:Messenger以串行的方式来处

随机推荐