共计 1786 个字符,预计需要花费 5 分钟才能阅读完成。
1 前言
我在很早之前的文章里,分享过有 C
语言手撸一个基于数组实现的最大堆,所以堆的根本实现思路和办法,不再赘述,详见:
数据与构造与算法: 堆 C 语言形容
C
语言可能受众小些,且稍微不太好了解,明天就用 JavaScript
形容一个最小堆,其实是基于最小堆的优先队列,不过两者基本上么有什么太大的区别,无非堆是存最根底的数字,优先队列则贮存的是一个构造体或者对象,有本人的key/value
,有本人的属性。
2 与 C
语言版本的不同
Js
的数组实质还是对象,长度是可变的,而C
语言的数组就是纯正的数组,一旦确定下来,长度就不可变。故而在C
版本中,咱们须要保护size
属性,不然不晓得数组到底应用到哪里了,这Js
版本就不须要,间接读取data.length
即可。- 自带函数,
Js
这种高级语言,自带很多函数,比方咱们应用pop()
函数就间接弹出了数组的开端,其长度主动减一,而C
语言版本显然没有这个性能
3 代码
var Heap = function () {this.data = []
this.insert = (obj) => {
let i = this.data.length
for (; i > 0 && this.data[Math.floor((i - 1) / 2)].val >= obj.val; i = Math.floor((i - 1) / 2)) {if (i < 1) {break}
this.data[i] = this.data[Math.floor((i - 1) / 2)]
}
this.data[i] = obj
}
this.pop = () => {if (this.data.length == 0) {return null}
if (this.data.length == 1) {return this.data.pop()
}
let top = this.data[0]
this.data[0] = this.data.pop()
let i = 0
while (2 * i + 1 < this.data.length) {if (2 * i + 2 < this.data.length) {if (this.data[2 * i + 2].val < this.data[i].val || this.data[2 * i + 1].val < this.data[i].val) {if (this.data[2 * i + 2].val < this.data[2 * i + 1].val) {this.swap(i, 2 * i + 2)
i = 2 * i + 2
} else {this.swap(i, 2 * i + 1)
i = 2 * i + 1
}
} else {break}
} else {if (this.data[2 * i + 1].val < this.data[i].val) {this.swap(i, 2 * i + 1)
i = 2 * i + 1
} else {break}
}
}
return top
}
this.swap = (i, j) => {let tmp = this.data[j]
this.data[j] = this.data[i]
this.data[i] = tmp
}
};
4 理论测试
测试代码如下
let obj = new Heap()
obj.insert({val: 19})
obj.insert({val: 10})
obj.insert({val: 11})
obj.insert({val: 19})
obj.insert({val: 100})
obj.insert({val: 18})
obj.insert({val: 200})
obj.insert({val: 18})
console.log(obj)
let len = obj.data.length
for (let index = 0; index < len; index++) {console.log(obj.pop())
}
以下为打印内容:
[Running] node "d:\Test\heap.js"
Heap {
data: [{ val: 10},
{val: 18},
{val: 11},
{val: 19},
{val: 100},
{val: 18},
{val: 200},
{val: 19}
],
insert: [Function (anonymous)],
pop: [Function (anonymous)],
swap: [Function (anonymous)]
}
{val: 10}
{val: 11}
{val: 18}
{val: 18}
{val: 19}
{val: 19}
{val: 100}
{val: 200}
[Done] exited with code=0 in 0.089 seconds
正文完