详解堆的javascript实现方法

前端之家收集整理的这篇文章主要介绍了详解堆的javascript实现方法前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。

堆的定义

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

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

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

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

基本操作

1、Build(构建堆)

2、Insert(插入)

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

代码实现

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

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

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

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

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

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

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

代码实现:

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]

[3]数据结构:堆

总结

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

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

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

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

原文链接:https://www.f2er.com/js/44083.html

猜你在找的JavaScript相关文章