数据结构与算法: 堆优先队列 JavaScript语言描述数据结构与算法堆优先队列

1 前言我在很早之前的文章里，分享过有C语言手撸一个基于数组实现的最大堆，所以堆的基本实现思路和方法，不再赘述，详见：
数据与结构与算法: 堆 C语言描述
【数据结构与算法: 堆优先队列 JavaScript语言描述】C语言可能受众小些，且略微不太好理解，今天就用JavaScript描述一个最小堆，其实是基于最小堆的优先队列，不过两者基本上么有什么太大的区别，无非堆是存最基础的数字，优先队列则储存的是一个结构体或者对象，有自己的key/value，有自己的属性。
2 与C语言版本的不同

Js的数组本质还是对象，长度是可变的，而C语言的数组就是纯粹的数组，一旦确定下来，长度就不可变。故而在C版本中，我们需要维护size属性，不然不知道数组究竟使用到哪里了，这Js版本就不需要，直接读取data.length即可。
自带函数，Js这种高级语言，自带很多函数，比如我们使用pop()函数就直接弹出了数组的末尾，其长度自动减一，而C语言版本显然没有这个功能

3 代码

var Heap = function () { this.data = https://www.it610.com/article/[] 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