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.lengthfor (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