乐趣区

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

jiezi

1 前言

我在很早之前的文章里，分享过有 C 语言手撸一个基于数组实现的最大堆，所以堆的根本实现思路和办法，不再赘述，详见：

数据与构造与算法: 堆 C 语言形容

C语言可能受众小些，且稍微不太好了解，明天就用 JavaScript 形容一个最小堆，其实是基于最小堆的优先队列，不过两者基本上么有什么太大的区别，无非堆是存最根底的数字，优先队列则贮存的是一个构造体或者对象，有本人的key/value，有本人的属性。

2 与 C 语言版本的不同

  1. Js的数组实质还是对象，长度是可变的，而 C 语言的数组就是纯正的数组，一旦确定下来，长度就不可变。故而在 C 版本中，咱们须要保护 size 属性，不然不晓得数组到底应用到哪里了，这 Js 版本就不须要，间接读取 data.length 即可。
  2. 自带函数，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
退出移动版