//优先队列 [最小]
//JavaScript 数组的长度和元素类型都是非固定的
class PriorityQuene{
constructor(){
//this.data = [1, 5, 2, 6, 7, 3, 8, 9, 10]
this.data = []
}
enQuene(key) {
this.data.push(key)
this.upAjust()
}
deQuene() {
let head = this.data[0]
this.downAdjust()
return head
}
upAjust() {
//获取新添加元素在数组中的下标
let childIndex = this.data.length - 1
//parent index
let parentIndex = parseInt((childIndex - 1) / 2)
//把新元素存起来,下边给它找到合适的位置放进去即可,这样效率比两个两个交换更高
let temp = this.data[childIndex]
while(childIndex > 0 && this.data[parentIndex] >= temp){
this.data[childIndex] = this.data[parentIndex]
childIndex = parentIndex
parentIndex = parseInt((parentIndex - 1) / 2)
}
this.data[childIndex] = temp
}
downAdjust(){
this.data[0] = this.data[this.data.length - 1]
this.data.splice(this.data.length - 1, 1)
let temp = this.data[0]
let parentIndex = 0
let childIndex = 2 * parentIndex + 1
while(childIndex < this.data.length){
//找到左右子树较小者的下标,推荐
if(childIndex + 1 < this.data.length && this.data[childIndex + 1] < this.data[childIndex]) {
childIndex ++
}
if(temp <= this.data[childIndex]){
break
}
this.data[parentIndex] = this.data[childIndex]
parentIndex = childIndex
childIndex = 2 * parentIndex + 1
}
this.data[parentIndex] = temp
}
printPriorityQuene(){
console.log(this.data)
}
}
let myPQ = new PriorityQuene()
/*
console.log(myPQ.deQuene())
myPQ.printPriorityQuene()
console.log(myPQ.deQuene())
myPQ.printPriorityQuene()
console.log(myPQ.deQuene())
myPQ.printPriorityQuene()
myPQ.enQuene(3)
myPQ.printPriorityQuene()
*/
//构建priorityQuene
myPQ.enQuene(10)
myPQ.enQuene(5)
myPQ.enQuene(2)
myPQ.enQuene(6)
myPQ.enQuene(7)
myPQ.enQuene(3)
myPQ.enQuene(8)
myPQ.enQuene(9)
myPQ.enQuene(1)
//打印构建好的队列
myPQ.printPriorityQuene()
console.log(myPQ.deQuene())
myPQ.printPriorityQuene()
console.log(myPQ.deQuene())
myPQ.printPriorityQuene()
console.log(myPQ.deQuene())
myPQ.printPriorityQuene()
本文由 dealdot ＜dealdot＃163.com＞ 创作, Full Stack Developer @ DeepBlue
本文最后编辑时间为: Jun 10, 2021 at 17:43 pm
转载请注明来源