JavaScript 百分网手机站

堆的javascript实现方法

时间:2018-06-02 20:40:03 JavaScript 我要投稿

堆的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],要求叶子节点从左往右填满,才能开始填充下一层,这就保证了不需要对数组整体进行大片的`移动。这也是随机存储结构(数组)的短板:删除一个元素之后,整体往前移是比较费时的。这个特性也导致堆在删除元素的时候,要把最后一个叶子节点补充到树根节点的缘由

  关于JavaScript的几点小结

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

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

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

  参考

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

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

  [3]数据结构:堆

【堆的javascript实现方法】相关文章:

1.Javascript到PHP加密通讯的简单实现方法

2.使用JavaScript实现Java的List功能

3.30行代码实现Javascript中的MVC

4.Javascript实现跨域的要点分析

5.javascript中的DOM方法

6.javascript的方法

7.Javascript加载方法

8.学习javascript的最佳方法