基于JS的優(yōu)先隊列實現(xiàn)
/**
* 優(yōu)先隊列
*/
class PriorityQueue {
constructor(compare,data) {
if(typeof compare !=='function'){
throw new Error('compare function required!')
}
if(data){
this.data = data
}else{
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
}
//取出最優(yōu)元素
pop() {
return this.data.pop()
}
//查看最優(yōu)元素
peek() {
return this.data[this.data.length - 1];
}
}
