超級醜數--用堆查找解決

利用堆排序很容易進行查找

質數又稱素數。一個大於1的自然數，除了1和它自身外，不能被其他自然數整除的數叫做質數；否則稱為合數。
質因數（素因數或質因數）在數論里是指能整除給定正整數的質數。除了1以外，兩個沒有其他共同質因數的正整數稱為互質。因為1沒有質因數，1與任何正整數（包括1本身）都是互質
把只包含質因數2、3和5的數稱作醜數（Ugly Number）。例如6、8都是醜數，但7.14不是，因為它們包含質因數7。 習慣上我們把1當做是第一個醜數

class Ugly {
  constructor (n, primes) {
    this.n = n
    this.primes = new Heap(primes)
  }
  getAll () {
    // 超級醜數列表
    let res = [1]
    let i = 2
    let primes = this.primes
    // 不知道上限用while迴圈
    while (res.length < this.n) {
      let arr = Ugly.getPrimies(i)
      let k = 0
      let l = arr.length
      for (; k < l; k++) {
        if (!primes.find(arr[k])) {
          break
        }
      }
      // k===l有兩種情況，1.壓根沒有質因數，2.質因數都在指定列表中
      if (k === l) {
        if (l === 0) {
          if (primes.find(i)) {
            res.push(i)
          }
        } else {
          res.push(i)
        }
      }
      i++
    }
    // 返回醜數數組
    return res[this.n - 1]
  }
  // 計算指定正整數n的質因數
  static getPrimies (n) {
    let prime = (n) => {
      let arr = []
      for (let i = 2; i < n / 2 + 1; i++) {
        // 求質數利用遞歸，因為返回的是一個arr數組,當數組為空時說明是質數
        if (n % i === 0 && !prime(i).length) {
          arr.push(i)
        }
      }
      return arr
    }
    return prime(n)
  }
}

class Heap {
  constructor (arr) {
    this.data = arr
    this.max = arr.length
    this.sort()
  }
  sort () {
    let iArr = this.data
    let n = iArr.length
    if (n <= 1) {
      return iArr
    } else {
      // 迴圈是為了遍歷每一個可能要調整的節點，maxHeapify內部遞歸是為了回覆被破壞的堆
      for (let i = Math.floor(n / 2); i >= 0; i--) {
        Heap.maxHeapify(iArr, i, n)
      }
      return iArr
    }
  }
  find (val, i = 0) {
    let arr = this.data
    if (val > arr[i] || i > this.max) {
      return false
    } else if (val === arr[i]) {
      return val
    } else {
      return this.find(val, i * 2 + 1) || this.find(val, i * 2 + 2)
    }
  }
  static swap (arr, a, b) {
    if (a === b) {
      return ''
    }
    // 交換
    let c = arr[a]
    arr[a] = arr[b]
    arr[b] = c
  }
  // 構建最大堆
  static maxHeapify (Arr, i, size) {
    // 左節點
    let l = i * 2 + 1
    // 右節點
    let r = i * 2 + 2
    let largest = i
    // 父節點和左節點l作比較獲取最大
    if (l <= size && Arr[l] > Arr[largest]) {
      largest = l
    }
    // 右節點額最大值比較
    if (r <= size && Arr[r] > Arr[largest]) {
      largest = r
    }
    if (largest !== i) {
      Heap.swap(Arr, i, largest)
      Heap.maxHeapify(Arr, largest, size)
    }
  }
}

export default Ugly
export {
  Heap
}