堆的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实现方法】相关文章：