观看数据结构堆一节，实现建堆build和max_heapify(i)操作，构建一个最大堆。

    1. class Heap {
    2.   constructor(data, Max = 10000){
    3.     this.list = Array(Max)
    4.     for(let i = 0; i < data.length; i++) {
    5.       this.list[i] = data[i]
    6.     }
    7.     this.heapSize = data.length
    8.     this.build()
    9.   }
    11.   build(){
    12.     /// TODO
    13.   }
    15.   max_heapify(i) {
    16.     /// TODO 
    17.   }
    18. }
    20. const heap = new Heap([2,5,8,3,7,12,9,6])
    21. console.log(heap.list)
    22. // [ 12, 7, 9, 6, 5, 8, 2, 3, <9992 empty items> ]

    答案:

    function swap(A, i, j) {
  const t = A[i]
  A[i] = A[j]
  A[j] = t
}
class Heap {
  constructor(data, Max = 10000){
    this.list = Array(Max)
    for(let i = 0; i < data.length; i++) {
      this.list[i] = data[i]
    }
    this.heapSize = data.length
    this.build()
  }

  build(){
    let i = Math.floor(this.heapSize / 2) - 1
    while(i >= 0) {
      this.max_heapify(i--)
    }
  }

  max_heapify(i) {
    const leftIndex = 2*i + 1
    const rightIndex = 2*i + 2
    let maxIndex = i
    if(leftIndex < this.heapSize && this.list[leftIndex] > this.list[maxIndex]) {
      maxIndex = leftIndex
    }
    if(rightIndex < this.heapSize && this.list[rightIndex] > this.list[maxIndex]) {
      maxIndex = rightIndex
    }
    if(i !== maxIndex) {
      swap(this.list, maxIndex, i)
      this.max_heapify(maxIndex)
    }
  }
}