用堆实现一个排序算法heap_sort(A)，对数组A进行排序

    答案:

    1. function swap(A, i, j) {
    2.   const t = A[i]
    3.   A[i] = A[j]
    4.   A[j] = t
    5. }
    6. class MaxHeap{
    7.   constructor(data){
    8.     this.list = data
    9.     this.heapSize = data.length
    10.     this.build()
    11.   }
    13.   build(){
    14.     let i = Math.floor(this.heapSize/2) - 1
    15.     while(i >= 0) {
    16.       this.max_heapify(i--)
    17.     }
    18.   }
    20.   extract() {
    21.     if (this.heapSize === 0) return null
    22.     const item = this.list[0]
    23.     swap(this.list, 0, this.heapSize - 1)
    24.     this.heapSize--
    25.     this.max_heapify(0)
    26.     return item
    27.   }
    29.   max_heapify(i) {
    30.     const leftIndex = 2*i + 1
    31.     const rightIndex = 2*i + 2
    32.     let maxIndex = i
    33.     if(leftIndex < this.heapSize && this.list[leftIndex] > this.list[maxIndex]) {
    34.       maxIndex = leftIndex
    35.     }
    36.     if(rightIndex < this.heapSize && this.list[rightIndex] > this.list[maxIndex]) {
    37.       maxIndex = rightIndex
    38.     }
    39.     if(i !== maxIndex) {
    40.       swap(this.list, maxIndex, i)
    41.       this.max_heapify(maxIndex)
    42.     }
    43.   }
    44. }
    46. function heap_sort(A){
    47.   const heap = new MaxHeap(A)
    48.   console.log(heap.list)
    49.   while(heap.heapSize > 0){
    50.     A[heap.heapSize-1] = heap.extract()
    51.   }
    52. }