javascript实现优先队列(入队,出队)

in 算法 with 0 comment
//优先队列 [最小]
  //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()

评论已关闭.