堆的javascript实现方法
来源:才华咖 本文已影响1.61W人
来源:才华咖 本文已影响1.61W人
堆的定义
最大(最小)堆是一棵每一个节点的键值都不小于(大于)其孩子(如果存在)的键值的树。大顶堆是一棵完全二叉树,同时也是一棵最大树。小顶堆是一棵完全完全二叉树,同时也是一棵最小树。
另外,记住这两个概念,对写代码太重要了:
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],要求叶子节点从左往右填满,才能开始填充下一层,这就保证了不需要对数组整体进行大片的`移动。这也是随机存储结构(数组)的短板:删除一个元素之后,整体往前移是比较费时的。这个特性也导致堆在删除元素的时候,要把最后一个叶子节点补充到树根节点的缘由
关于JavaScript的几点小结
这里是采用面向对象的一种实现方法,感觉上不是太优雅,不知道还有没有更好的表示方法和写法;
学习了数组的几个用法:push和pop的操作太好用了;
判断数组的方式也是临时从网上搜的(instanceof),印象不深刻,不用的话下次估计还是有可能忘掉。
参考
[1]《数据结构和算法分析:C语言描述》
[2]图解数据结构(8)——二叉堆
[3]数据结构:堆
关于JavaScript substring()的使用方法
javasc ript 返回上一页及刷新页面的实现方法
30行代码实现Javascript中的MVC
详解JavaScript中的splice()使用方法
Javascript中arguments对象的详解和使用方法
JavaScript类定义原型方法的两种实现的区别
JavaScript instanceof 的使用方法有哪些
关于JavaScript中的parse()的使用方法
关于 response方法的javascript asp教程第六课
JavaScript如何实现JSON.stringify
如何在Javascript中为String对象添加trim,ltrim,rtrim方法
用 Javascript 实现锚点(Anchor)间平滑跳转
Javascript拓展String方法代码
javascript中String对象的slice()方法
java使用ConcurrentHashMap和计数器实现锁的方法
获取JavaScript中的方法
有关javascript在IE下trim函数无法使用的解决方法
2017最新javascript中AJAX用法
高学历实现跳槽成功方法
深入理解JS实现快速排序和去重javascript技巧
javascript中setInterval的用法总结
jQuery 和其他 JavaScript 框架使用方法
Javascript加载方法
Javascript 继承实现例子参考
现实表现材料写作方法与要求
JavaScript-JavaScript数据结构和算法之图和图算法,
JavaScript重置表单的实现
java与javascript之间json格式数据互转详解
Javascript和Java语言间的异同比较
堆的javascript实现方法
JavaScript中创建字典对象(dictionary)的实例
在JavaScript中操作数组之map()方法的使用示例
实现作文教学的创新的方法
javascript实现贪吃蛇代码
Javascript实现跨域的要点分析
JavaScript与java语言的区别
JavaScript toFixed方法介绍
php和javascript之间变量的传递实现代码
Javascript到PHP加密通讯的简单实现
Javascript时间格式format函数的两种使用方法