大家好，我是 17
优先队列中的每个元素都有各自的优先级，优先级最高的元素最先得到服务；优先级相同的元素按照其在优先队列中的顺序得到服务。
优先队列至少需要支持下述操作：
- 插入带优先级的元素（insert_with_priority）
- 取出具有最高优先级的元素（pull_highest_priority_element）
- 查看最高优先级的元素（peek）：O(1) 时间复杂度
其它语言一般都有相应的函数，可惜 js 没有，所以补上一个。
class PriorityQueue { constructor(compare) { if(typeof compare !=='function'){ throw new Error('compare function required!') } this.data = [] this.compare = compare } //二分查找 寻找插入位置 search(target) { let low = 0, high = this.data.length while (low < high) { let mid = low + ((high - low) >> 1) if (this.compare(this.data[mid], target) > 0) { high = mid } else { low = mid + 1 } } return low; } //添加 push(elem) { let index = this.search(elem) this.data.splice(index, 0, elem) return this.data.length } //取出最优元素 pop() { return this.data.pop() } //查看最优元素 peek() { return this.data[this.data.length - 1]; } } 复制代码
先不要看代码实现，把 PriorityQueue 当作黑盒看看怎么使用。
最大值最小值优先
每次取出的是整个队列中的最小值。为了达到这个目的，队列是有序的，且升序排列。
拿实际值演练一下。
let qeen = new PriorityQueue((a, b) => a-b) queen.push(3); console.log(queen.data) //[3] queen.push(1); console.log(queen.data) //[1,3] qeeun.push(2); console.log(queen.data) //[1,2,3] 复制代码
每次播入新元素，都会自动把元素插入到正确的位置，保持队列按升序排列，关键就在于 (a,b) => a-b 这个 compare 方法 是这经告诉 PriorityQueue 如何插入元素。这个compare 方法和 Array的 sort 方法用的 compare 是一样的,是为了好记，只要会sort 方法，就会用 PriorityQueue
let arr = [1, 3, 2] //按升序 arr.sort((a, b) => a - b) // [1,2,3] //优先队列的数据按升序排列 let qeen = new PriorityQueue((a, b) => a - b) queen.push(3); queen.push(2); queen.push(1); consolelog(queen.data) //[ 1，2，3 ] //按降序 arr.sort((a, b) => b - a) // [3,2,1] //优先队列的数据按降序排列 let qeen = new PriorityQueue((a, b) => b - a) 复制代码
PriorityQueue 是特意采用数组已有的方法名，就是为了好记。
除了 push pop peek，还有 search 方法也是公开的，而且查找速度也是很快的。如果不知道目标元素的 index,只知道值，可以用 search 查找。
注意 search 找到的是播入位置
复杂度
时间复杂度
- pop O(1)
- peek O(1)
- push O(n),
- search O(logn)
有的同学这样写的，没有用 splice 方法
//从小到大排列,播入元素，向前冒泡 function insert(n) { this.data.push(n); let len = this.data.len while (len-- > 0) { if (this.data[len] < this.data[len - 1]) { //交换 [this.data[len], this.data[len - 1]] = [this.data[len - 1], this.data[len]] } else { break } } } 复制代码
理由是 既然 splice 方法最后也是 O(n)，我这样也是 O(n)。但实际上 splice 方法在速度比这样循环要快多了。
虽然在插入的时候较慢，但取出数据的时候是 O(1)，取 前 N 个数据的时间也比树快。
如果要优化插入的时间，可以用红黑树，但取出数据后还得维护树， 插入，取（删除）都是 O(logn)。而且用树的话，就不能通过 index 用 O(1) 的时间来找到元素了。
所以当前版本的 PriorityQueue 还是可以优先考虑的。
空间复杂度
data存的值不算，额外的空间为 O(1)
最后提醒一下，PriorityQueue 不是光能存数字，是可以存对象的。只要给出 比较对象的方法即可，和数组的 sort 方法一样。
